﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using std::cout;
using std::endl;

//using namespace std;
////
////////JZ64 求1 + 2 + 3 + ... + n
////////求1 + 2 + 3 + ... + n，要求不能使用乘除法、位操作符、for、while、if、else、switch、case等关键字及条件判断语句（A ? B : C）。
//////class A
//////{
//////public:
//////    A()
//////    {
//////        sum += c;
//////        c++;
//////    }
//////    //静态成员变量只能用静态成员函数访问到
//////    static int Getsum()
//////    {
//////        return sum;
//////    }
//////private:
//////    //声明两个静态成员，一个用于存总值，一个当做从1开始不断+1的变化值。
//////    static int sum;
//////    static int c;
//////};
////////定义静态成员变量
//////int A::sum = 0;
//////int A::c = 1;
////////使用静态成员变量
//////class Solution {
//////public:
//////    int Sum_Solution(int n) {
//////        A a1[n];//变长数组
//////        return A::Getsum();
//////    }
//////};
//////
//////
//////
////////HJ73 计算日期到天数转换
////////根据输入的日期，计算是这一年的第几天。
////////保证年份为4位数且日期合法。
//////int main()
//////{
//////    int arr[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
//////    int year, month, day;
//////    cin >> year >> month >> day;
//////    if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
//////    {
//////        arr[1]++;
//////    }
//////    int sum = 0;
//////    for (int i = 0; i < month - 1; i++)
//////    {
//////        sum += arr[i];
//////    }
//////    sum += day;
//////    cout << sum << endl;
//////}
//////
//////
//////
////////KY222 打印日期
////////给出年分m和一年中的第n天，算出第n天是几月几号。
//////int main() {
//////    int year, day;
//////    while (cin >> year >> day) { // 注意 while 处理多个 case
//////        int arr[12] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
//////        if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
//////        {
//////            arr[1]++;
//////        }
//////        int month = 1;
//////        int i = 0;
//////        while (day > arr[i])
//////        {
//////            month++;
//////            day -= arr[i++];
//////        }
//////        printf("%d-%02d-%02d\n", year, month, day);
//////    }
//////}
////
////
//////KY111 日期差值
//////有两个日期，求两个日期之间的天数，如果两个日期是连续的我们规定他们之间的天数为两天
//////用日期类来实现
////class Date
////{
////public:
////	Date(int year = 1, int month = 1, int day = 1)
////		:_year(year),
////		_month(month),
////		_day(day)
////	{}
////	// 获取某年某月的天数
////	int GetMonthDay(int year, int month)
////	{
////		int monthday[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
////		if (month == 2)
////		{
////			if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
////			{
////				return 29;
////			}
////			else
////				return 28;
////		}
////		return monthday[month];
////	}
////	// 日期+=天数
////	Date& operator+=(int day)
////	{
////		_day += day;
////		while (_day > GetMonthDay(_year, _month))
////		{
////			_day -= GetMonthDay(_year, _month);
////			_month++;
////			if (_month > 12)
////			{
////				_month = 1;
////				_year++;
////			}
////		}
////		return *this;
////	}
////	// 日期+天数
////	Date operator+(int day)
////	{
////		Date tmp = *this;
////		tmp += day;
////		return tmp;
////	}
////	// 日期-天数
////	Date operator-(int day)
////	{
////		Date tmp = *this;
////		tmp -= day;
////		return tmp;
////	}
////	// 日期-=天数
////	Date& operator-=(int day)
////	{
////		_day -= day;
////		while (day < 1)
////		{
////			_month--;
////			if (_month < 1)
////			{
////				_month = 12;
////				_year--;
////
////			}
////			_day += GetMonthDay(_year, _month);
////		}
////		return *this;
////	}
////	// 前置++
////	Date& operator++()
////	{
////		(*this) += 1;
////		return *this;
////	}
////	// 后置++
////	Date operator++(int)
////	{
////		Date tmp = *this;
////		(*this) += 1;
////		return tmp;
////	}
////	// 后置--
////	Date operator--(int)
////	{
////		Date tmp = *this;
////		(*this) -= 1;
////		return tmp;
////	}
////	// 前置--
////	Date& operator--()
////	{
////		(*this) -= 1;
////		return *this;
////	}
////	// >运算符重载
////	bool operator>(const Date& d)
////	{
////		if (_year > d._year)
////			return true;
////		else if (_year == d._year)
////		{
////			if (_month > d._month)
////				return true;
////			else if (_month == d._month)
////			{
////				if (_day > d._day)
////					return true;
////				else
////					return false;
////			}
////			else
////				return false;
////		}
////		else
////			return false;
////	}
////	// ==运算符重载
////	bool operator==(const Date& d)
////	{
////		if (_year == d._year && _month == d._month && _day == d._day)
////		{
////			return true;
////		}
////		return false;
////	}
////	// >=运算符重载
////	bool operator >= (const Date& d)
////	{
////		if ((*this) > d || (*this) == d)
////			return true;
////		return false;
////	}
////	// <运算符重载
////	bool operator < (const Date& d)
////	{
////		if (_year < d._year)
////			return true;
////		else if (_year == d._year)
////		{
////			if (_month < d._month)
////				return true;
////			else if (_month == d._month)
////			{
////				if (_day < d._day)
////					return true;
////				else
////					return false;
////			}
////			else
////				return false;
////		}
////		else
////			return false;
////	}
////	// <=运算符重载
////	bool operator <= (const Date& d)
////	{
////		if ((*this) < d || (*this) == d)
////			return true;
////		return false;
////	}
////	// !=运算符重载
////	bool operator != (const Date& d)
////	{
////		if ((*this) == d)
////			return false;
////		return true;
////	}
////	// 日期-日期 返回天数
////	int operator-(const Date& d)
////	{
////		int num = 0;
////		if ((*this) <= d)
////		{
////			Date tmp = (*this);
////			while (tmp != d)
////			{
////				++tmp;
////				num++;
////			}
////		}
////		else
////		{
////			Date tmp = d;
////			while (tmp != (*this))
////			{
////				++tmp;
////				num++;
////			}
////		}
////		return num;
////	}
////private:
////	int _year;
////	int _month;
////	int _day;
////};
//////int main() {
//////	// char year1[4],month1[2],day1[2];
//////	// char year2[4],month2[2],day2[2];
//////	int year1 = 0, month1 = 0, day1 = 0;
//////	int year2 = 0, month2 = 0, day2 = 0;
//////	char arr[2][9];
//////	//第一行转int
//////	for (int i = 0; i < 2; i++)
//////	{
//////		cin >> arr[i];
//////	}
//////	for (int i = 0; i < 4; i++)
//////	{
//////		year1 += (arr[0][i] - '0') * pow(10, 3 - i);
//////	}
//////	for (int i = 4; i < 6; i++)
//////	{
//////		month1 += (arr[0][i] - '0') * (int)pow(10, 5 - i);
//////	}
//////	for (int i = 6; i < 8; i++)
//////	{
//////		day1 += (arr[0][i] - '0') * pow(10, 7 - i);
//////	}
//////	//第二行转int
//////	for (int i = 0; i < 4; i++)
//////	{
//////		year2 += (arr[1][i] - '0') * pow(10, 3 - i);
//////	}
//////	for (int i = 4; i < 6; i++)
//////	{
//////		month2 += (arr[1][i] - '0') * (int)pow(10, 5 - i);
//////	}
//////	for (int i = 6; i < 8; i++)
//////	{
//////		day2 += (arr[1][i] - '0') * pow(10, 7 - i);
//////	}
//////	//printf("%s\n",arr[0]);
//////	//printf("%d %0d %0d\n",year1,month1,day1);
//////   // printf("%d %0d %0d\n",year2,month2,day2);
//////	Date n1(year1, month1, day1);
//////	Date n2(year2, month2, day2);
//////	int ret = n1 - n2 + 1;
//////	printf("%d", ret);
//////}
////
////
//////
////////KY258 日期累加
////////设计一个程序能计算一个日期加上若干天后是什么日期。
//////int Getmothday(int year, int month)
//////{
//////	int arr[13] = { 31,28,31,30,31,30,31,31,30,31,30,31 };
//////	if ((year % 400 == 0) || (year % 4 == 0 && year % 100 != 0))
//////	{
//////		arr[1]++;
//////	}
//////	return arr[month - 1];
//////}
//////int main() {
//////	int num;
//////	cin >> num;
//////	while (num--) { // 注意 while 处理多个 case
//////		int year, month, day, add;
//////		cin >> year >> month >> day >> add;
//////		day += add;
//////		while (day > Getmothday(year, month))
//////		{
//////			day -= Getmothday(year, month);
//////			month++;
//////			if (month > 12)
//////			{
//////				month = 1;
//////				year++;
//////			}
//////		}
//////		printf("%d-%02d-%02d\n", year, month, day);
//////	}
//////}
////
////
////
////int globalVar = 1;
////static int staticGlobalVar = 1;
////void Test()
////{
////	static int staticVar = 1;
////	int localVar = 1;
////	int num1[10] = { 1, 2, 3, 4 };
////	char char2[] = "abcd";
////	const char* pChar3 = "abcd";
////	int* ptr1 = (int*)malloc(sizeof(int) * 4);
////	int* ptr2 = (int*)calloc(4, sizeof(int));
////	int* ptr3 = (int*)realloc(ptr2, sizeof(int) * 4);
////	free(ptr1);
////	free(ptr3);
////}
//////1. 选择题：
//////选项 : A.栈 B.堆 C.数据段(静态区) D.代码段(常量区)
//////globalVar在哪里？__C__  staticGlobalVar在哪里？_C___
//////staticVar在哪里？__C__  localVar在哪里？_A___
//////num1 在哪里？_A___
//////
//////char2在哪里？_A___ * char2在哪里？__A_（用数组存储字符串，会在代码段生成一串字符，然后到栈上开辟一段空间，把内容拷贝进去）
//////pChar3在哪里？_A___ * pChar3在哪里？_D___（用指针则是存放 代码段内存放字符串的地址，所以解引用后地址会在代码段）
//////ptr1在哪里？__A__ * ptr1在哪里？_B___（prt1变量是在栈区创建的，所以在栈上，但申请的空间在堆上）
//////
//////2. 填空题：
//////sizeof(num1) = __40__;
//////sizeof(char2) = _5___;   strlen(char2) = __4__;（sizeof（数组）就是整个数组的大小）
//////sizeof(pChar3) = _4/8___;   strlen(pChar3) = _4___;（sizeof（指针）则是看几位计算机）
//////sizeof(ptr1) = __4/8__;
////
////
////
////
////////LCR 192. 把字符串转换成整数
////////函数 myAtoi(string s) 的算法如下：
////////读入字符串并丢弃无用的前导空格
////////检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
////////读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
////////将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
////////如果整数数超过 32 位有符号整数范围[−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。
////////具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
////////返回整数作为最终结果。
//////class Solution {
//////public:
//////	int myAtoi(string str) {
//////		int flag = 1; int time = 0;
//////		long int sum = 0;
//////		int i = 0;
//////		while (str[i] == ' ')
//////		{
//////			i++;
//////		}
//////		while (str[i] < '0' || str[i]>'9')
//////		{
//////			if (str[i] == '-')
//////			{
//////				flag *= -1;
//////				i++;
//////				time++;
//////				if (time > 1)
//////					return 0;
//////			}
//////			else if (str[i] == '+')
//////			{
//////				i++;
//////				time++;
//////				if (time > 1)
//////					return 0;
//////			}
//////			else
//////				return 0;
//////		}
//////		while (str[i] >= '0' && str[i] <= '9')
//////		{
//////			sum *= 10;
//////			sum += str[i] - '0';
//////			i++;
//////			if (sum > (long int)pow(2, 31) - 1)
//////			{
//////				if (flag == 1)
//////					return INT_MAX;
//////				else
//////					return INT_MIN;
//////			}
//////		}
//////		sum *= flag;
//////		return sum;
//////	}
//////};
//////
//////
//////
////////344. 反转字符串
////////编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。
////////不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
//////class Solution {
//////public:
//////	void reverseString(vector<char>& s) {
//////		std::vector<char>::iterator it1 = s.begin();
//////		std::vector<char>::iterator it2 = s.end();
//////		//end为最后一个元素的下一个位置，所以要在-1
//////		it2--;
//////		int time = s.size() / 2;
//////		while (time--)
//////		{
//////			swap(*it1, *it2);
//////			it1++;
//////			it2--;
//////		}
//////	}
//////};
//////
//////
//////
//////
////////415. 字符串相加
////////给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。
////////你不能使用任何內建的用于处理大整数的库（比如 BigInteger）， 也不能直接将输入的字符串转换为整数形式。
//////class Solution {
//////public:
//////	string addStrings(string num1, string num2) {
//////		//jin表示进位，sum表示当前两个数的总和，也可以作为余数
//////		int jin = 0, sum = 0;
//////		string ret;
//////		//手动开辟空间，提高效率
//////		ret.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);
//////		int i = num1.size() - 1;
//////		int j = num2.size() - 1;
//////		while (i >= 0 || j >= 0)
//////		{
//////			//left和right存放num1和num2当前字符转换为整形的值
//////			//如果其中一个字符访问没了，而另一个字符还有；则没了的字符串就返回0，方便计算
//////			int left = i >= 0 ? num1[i--] - '0' : 0;
//////			int right = j >= 0 ? num2[j--] - '0' : 0;
//////			//num1的数+num2的数+进位
//////			sum = left + right + jin;
//////			jin = sum / 10;
//////			sum = sum % 10;//取余就是留下要转为字符的那个数字
//////			ret += sum + '0';
//////		}
//////		//如果最后进位还有个1，则也要加上
//////		if (jin == 1)
//////			ret += jin + '0';
//////		//由于前面我们的ret字符串是用+=实现的，+=的内核是尾插，所以ret要翻转一下
//////		std::string::iterator it1 = ret.begin();
//////		std::string::iterator it2 = ret.end();
//////		//调用库函数reverse，reverse的两个传参需要是迭代器
//////		reverse(it1, it2);
//////		return ret;
//////	}
//////};
////
////
////
////////387.字符串中的第一个唯一字符
////////给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 - 1 。
//////class Solution {
//////public:
//////	int firstUniqChar(string s) {
//////		int arr[123] = { 0 };
//////		for (int i = 0; i < s.size(); i++)
//////		{
//////			arr[s[i]]++;
//////		}
//////		for (int i = 0; i < s.size(); i++)
//////		{
//////			if (arr[s[i]] == 1)
//////				return i;
//////		}
//////		return -1;
//////	}
//////};
////
////
////
////////125. 验证回文串
////////如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
////////字母和数字都属于字母数字字符。
////////给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。
//////class Solution {
//////public:
//////	bool isPalindrome(string s) {
//////		string ret;
//////		ret.reserve(s.size() + 1);
//////		//int j=0;
//////		for (int i = 0; i < s.size(); i++)
//////		{
//////			if (s[i] >= 'a' && s[i] <= 'z')
//////			{
//////				ret += s[i];
//////			}
//////			else if (s[i] >= 'A' && s[i] <= 'Z')
//////			{
//////				ret += s[i] + 32;
//////			}
//////			else if (s[i] >= '0' && s[i] <= '9')
//////			{
//////				ret += s[i];
//////			}
//////		}
//////		int i = 0, j = ret.size() - 1;
//////		while (i <= j)
//////		{
//////			if (ret[i] == ret[j])
//////			{
//////				i++; j--;
//////			}
//////			else
//////				return false;
//////		}
//////		return true;
//////	}
//////};
//
//
//
//////HJ1 字符串最后一个单词的长度
//////计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
////int main() {
////    string str;
////    getline(cin, str);
////    int pos = str.rfind(' ');
////    cout << str.size() - pos - 1 << endl;
////}
//
//
//////541. 反转字符串 II
//////给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。
//////如果剩余字符少于 k 个，则将剩余字符全部反转。
//////如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
////class Solution {
////public:
////    string reverseStr(string s, int k) {
////        std::string::iterator it1 = s.begin();
////        std::string::iterator it2 = s.begin();
////        int i = 0;
////        while ((*it1) != '\0')
////        {
////            i++;
////            if (i == 2 * k)
////            {
////                //reverse必须是左闭右开的区间，所以后面it2赋值后+1
////                reverse(it2, it2 + k);
////                i = 0;
////                it2 = it1 + 1;
////            }
////            it1++;
////        }
////        if (i != 0)
////        {
////            if (i < k)
////            {
////                reverse(it2, it1);
////            }
////            else
////            {
////                reverse(it2, it2 + k);
////            }
////        }
////        return s;
////    }
////};
////
////
////
//////557. 反转字符串中的单词 III
//////给定一个字符串 s ，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
////class Solution {
////public:
////    string reverseWords(string s) {
////        std::string::iterator it1 = s.begin();
////        std::string::iterator it2 = s.begin();
////        while (*it1 != '\0')
////        {
////            if (*it1 == ' ')
////            {
////                reverse(it2, it1);
////                it2 = it1 + 1;
////            }
////            it1++;
////        }
////        reverse(it2, it1);
////        return s;
////    }
////};
//
//
//
//
////class Solution {
////public:
////    string multiply(string num1, string num2) {
////        int jin = 0;
////        int sum = 0;
////        string ret;
////        //ret.reserve(num1.size()>num2.size()?num1.size()+1:num2.size()+1);
////        int i = 0;
////        while (i < num1.size())
////        {
////            int j = 0;
////            int right = num1[i] - '0';
////            while (j < num2.size())
////            {
////                int left = num2[j] - '0';
////                //int right=num1[i]-'0';
////                sum = left * right + jin;
////                jin = sum / 10;
////                sum = sum % 10;
////                ret += sum + '0';
////                j++;
////            }
////            i++;
////        }
////        return ret;
////    }
////};
////int main()
////{
////    Solution a1;
////    string s1 = "123";
////    string s2 = "6";
////    a1.multiply(s2,s1);
////
////}
//
//
//////43. 字符串相乘
//////给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
//////注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
////class Solution {
////public:
////    string addStrings(string num1, string num2) {
////        //jin表示进位，sum表示当前两个数的总和，也可以作为余数
////        int jin = 0, sum = 0;
////        string ret;
////        //手动开辟空间，提高效率
////        ret.reserve(num1.size() > num2.size() ? num1.size() + 1 : num2.size() + 1);
////        int i = num1.size() - 1;
////        int j = num2.size() - 1;
////        while (i >= 0 || j >= 0)
////        {
////            //left和right存放num1和num2当前字符转换为整形的值
////            //如果其中一个字符访问没了，而另一个字符还有；则没了的字符串就返回0，方便计算
////            int left = i >= 0 ? num1[i--] - '0' : 0;
////            int right = j >= 0 ? num2[j--] - '0' : 0;
////            //num1的数+num2的数+进位
////            sum = left + right + jin;
////            jin = sum / 10;
////            sum = sum % 10;//取余就是留下要转为字符的那个数字
////            ret += sum + '0';
////        }
////        //如果最后进位还有个1，则也要加上
////        if (jin == 1)
////            ret += jin + '0';
////        //由于前面我们的ret字符串是用+=实现的，+=的内核是尾插，所以ret要翻转一下
////        std::string::iterator it1 = ret.begin();
////        std::string::iterator it2 = ret.end();
////        //调用库函数reverse，reverse的两个传参需要是迭代器
////        reverse(it1, it2);
////        return ret;
////    }
////    //123
////    //456
////    //步骤：tmp=123*6，ret=ret+tmp,用上述字符串加法实现
////    //然后重新tmp=123*5+‘0’，ret=ret+tmp
////    //最后tmp=123*4,+‘00’，ret=ret+tmp
////    string multiply(string num1, string num2) {
////        int jin = 0;
////        int sum = 0;
////        string ret = "0";//表示初值
////        if (ret.compare(num1) == 0 || ret.compare(num2) == 0)
////            return ret;
////        //ret.reserve(num1.size()>num2.size()?num1.size()+1:num2.size()+1);
////        int i = num1.size() - 1;
////        //遍历num1
////        while (i >= 0)
////        {
////            sum = 0;//存放两个单独的数字的合值和要加入ret的个位数
////            jin = 0;//存放进位的数字
////            string tmp;//存放每次相乘得到的字符
////            int j = num2.size() - 1;//j每次从末尾遍历
////            int right = num1[i] - '0';//存放i位置的值
////            //遍历num2
////            while (j >= 0)
////            {
////                int left = num2[j] - '0';
////                sum = left * right + jin;
////                jin = sum / 10;
////                sum = sum % 10;
////                tmp += sum + '0';
////                j--;
////            }
////            //加上进位的数字
////            if (jin >= 1)
////            {
////                tmp += jin + '0';
////            }
////            //翻转tmp，因为我们上面是+=得到的
////            reverse(tmp.begin(), tmp.end());
////            int k = num1.size() - 1 - i;//根据i的遍历剩余次数在后面+‘0’
////            while (k--)
////            {
////                tmp += '0';
////            }
////            ret = addStrings(ret, tmp);
////            i--;
////        }
////        return ret;
////    }
////};
//
//
////1544. 整理字符串
////给你一个由大小写英文字母组成的字符串 s 。
////一个整理好的字符串中，两个相邻字符 s[i] 和 s[i + 1]，其中 0 <= i <= s.length - 2 ，要满足如下条件:
////若 s[i] 是小写字符，则 s[i + 1] 不可以是相同的大写字符。
////若 s[i] 是大写字符，则 s[i + 1] 不可以是相同的小写字符。
////请你将字符串整理好，每次你都可以从字符串中选出满足上述条件的 两个相邻 字符并删除，直到字符串整理好为止。
////请返回整理好的 字符串 。题目保证在给出的约束条件下，测试样例对应的答案是唯一的。
////注意：空字符串也属于整理好的字符串，尽管其中没有任何字符。
//class Solution {
//public:
//    bool Ishave(string& s)
//    {
//        //如果s被删空了，直接返回false
//        if (s == "")
//            return false;
//        //在s中找符合题意的字符并删除，若删除了，则返回1，让下面的循环继续
//        for (int i = 0; i < s.size() - 1; i++)
//        {
//            if (s[i] + 32 == s[i + 1] || s[i] - 32 == s[i + 1])
//            {
//                s.erase(i, 2);
//                return true;
//            }
//        }
//        return false;
//    }
//    string makeGood(string s) {
//        int ret = Ishave(s);//用于循环判断是否还有符合题意的字符
//        while (ret)
//        {
//            ret = Ishave(s);
//        }
//        return s;
//    }
//};
//
//////测试
////int main()
////{
////    Solution s;
////    string s1("abBAcC");
////    s.makeGood(s1);
////    return 0;
////}
////
//
//
////
//////136. 只出现一次的数字
////class Solution {
////public:
////    int singleNumber(vector<int>& nums) {
////        int sum = 0;
////        for (int i = 0; i < nums.size(); i++)
////        {
////            sum ^= nums[i];
////        }
////        return sum;
////    }
////};
////
////
////
//////pta6 - 1 修改学生成绩
//////输入n(n < 50)个学生的成绩信息，再输入一个学生的学号、课程以及成绩，在自定义函数update_score()中修改该学生指定课程的成绩。
////int update_score(struct student* p, int n, int num, int course, int score)
////{
////    for (int i = 0; i < n; i++)
////    {
////        if (p[i].num == num)
////        {
////            if (course == 1)
////            {
////                p[i].math = score;
////            }
////            else if (course == 2)
////            {
////                p[i].english = score;
////            }
////            else
////            {
////                p[i].computer = score;
////            }
////            return i;
////        }
////    }
////    return -1;
////}
////
////
//////pta 7 - 1 查找书籍
//////给定n本书的名称和定价，本题要求编写程序，查找并输出其中定价最高和最低的书的名称和定价。
////struct book
////{
////    char name[31];
////    double m;
////};
////int main()
////{
////    int n;
////    scanf("%d\n", &n);
////    struct book b1[n];
////    for (int i = 0; i < n; i++)
////    {
////        int j = 0;
////        char tmp = getchar();
////        while (tmp != '\n')
////        {
////            b1[i].name[j] = tmp;
////            j++;
////            tmp = getchar();
////        }
////        b1[i].name[j] = '\0';
////        scanf("%lf\n", &b1[i].m);
////    }
////    // for(int i=0;i<n;i++)
////    // {
////    //     printf("%lf, %s\n",b1[i].m,b1[i].name);
////    // }
////    for (int i = 0; i < n; i++)
////    {
////        for (int j = 0; j < n - 1 - i; j++)
////        {
////            if (b1[j].m < b1[j + 1].m)
////            {
////                struct book tmp = b1[j];
////                b1[j] = b1[j + 1];
////                b1[j + 1] = tmp;
////            }
////        }
////    }
////    printf("%.2lf, %s\n", b1[0].m, b1[0].name);
////    printf("%.2lf, %s\n", b1[n - 1].m, b1[n - 1].name);
////    return 0;
////}
////
////
////
//////杨辉三角
//////理解resize和reserve的开空间的差别
////class Solution {
////public:
////    vector<vector<int>> generate(int numRows) {
////        vector<vector<int>> v1;
////        //用resize，因为reserve只开空间，实际v1的size没有变化，就不能访问到后面的空间
////        //v1.reserve(numRows)
////        v1.resize(numRows);
////        for (int i = 0; i < numRows; i++)
////        {
////            //同理，也只能用resize开空间
////            v1[i].resize(i + 1);
////            for (int j = 0; j <= i; j++)
////            {
////                if (j == 0)
////                {
////                    v1[i][j] = 1;
////                }
////                else if (j == i)
////                {
////                    v1[i][j] = 1;
////                }
////                else
////                {
////                    v1[i][j] = v1[i - 1][j - 1] + v1[i - 1][j];
////                }
////            }
////        }
////        return v1;
////    }
////};
//
//
//
////
//////137. 只出现一次的数字 II
//////给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
//////你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。
////class Solution {
////public:
////    int singleNumber(vector<int>& nums) {
////        int ret = 0;
////        // 把每个数的二进制位分开来，访问每个二进制位的数字
////        // 例如：2 2 3 2
////        //     0 0 1 0
////        //     0 0 1 0
////        //     0 0 1 1
////        //     0 0 1 0
////        //遍历数组每个数的第0位，观察出现1的个数，如果不是3的倍数，则说明单个数字的这个二进制位为1
////        // 总共访问32位
////        for (int i = 0; i < 32; i++)
////        {
////            //存放整个数组中的，当前i二进制位出现1的个数
////            int tmp = 0;
////            //遍历数组
////            for (int j = 0; j < nums.size(); j++)
////            {
////                //取当前位是否为1，为1加入tmp中
////                tmp += (nums[j] >> i) & 1;
////            }
////            //因为重复的数会出现3次，如果是重复的数的i二进制位模3后就会为0，出现单个的数字才会
////            tmp %= 3;
////            if (tmp == 1)
////            {
////                //前面右移了i为，这里把当前位移回来
////                ret += tmp << i;
////            }
////        }
////        return ret;
////    }
////};
////
////
//////260. 只出现一次的数字 III
//////给你一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。
//////你必须设计并实现线性时间复杂度的算法且仅使用常量额外空间来解决此问题。
//////时间复杂度O(N^2)   空间复杂度O(N)
////class Solution {
////public:
////    vector<int> singleNumber(vector<int>& nums) {
////        vector<int> ret;
////        ret.reserve(nums.size());
////        ret.push_back(nums[0]);
////        for (int i = 1; i < nums.size(); i++)
////        {
////            int flag = 0;
////            std::vector<int>::iterator j = ret.begin();
////            for (j; j < ret.end(); j++)
////            {
////                if (*j == nums[i])
////                {
////                    ret.erase(j);
////                    flag = 1;
////                    break;
////                }
////            }
////            if (flag == 0)
////            {
////                ret.push_back(nums[i]);
////            }
////        }
////        return ret;
////    }
////};
////
//////26. 删除有序数组中的重复项
//////给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 
//////返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
//////考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
//////更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
//////返回 k 。
////class Solution {
////public:
////    int removeDuplicates(vector<int>& nums) {
////        int i = 0, j = 1;
////        while (i < nums.size() && j < nums.size())
////        {
////            if (nums[i] == nums[j])
////            {
////                j++;
////            }
////            else
////            {
////                i++;
////                nums[i] = nums[j];
////                j++;
////            }
////        }
////        return i + 1;
////    }
////};
////
////
////
//////牛客N
//////JZ39 数组中出现次数超过一半的数字
//////解法1：时间复杂度O(N)，空间复杂度O(N)
//////给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
////class Solution {
////public:
////    /**
////     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
////     *
////     *
////     * @param numbers int整型vector
////     * @return int整型
////     */
////    int MoreThanHalfNum_Solution(vector<int>& numbers) {
////        // write code here
////        int arr[10001] = { 0 };
////        for (int i = 0; i < numbers.size(); i++)
////        {
////            arr[numbers[i]]++;
////        }
////        int i = 0;
////        for (i = 0; i < 10000; i++)
////        {
////            if (arr[i] > numbers.size() / 2)
////            {
////                break;
////            }
////        }
////        return i;
////    }
////};
//////解法2：时间复杂度O(N)，空间复杂度O(1)
////int MoreThanHalfNum_Solution(vector<int>& numbers) {
////    // write code here
////    int hou = numbers[0];//候选人
////    int num = 1;//候选人出现次数
////
////    for (int i = 1; i < numbers.size(); i++)
////    {
////        //更换候选人
////        if (num == 0)
////        {
////            hou = numbers[i];
////            num = 1;
////        }
////        else {
////            //判断当前的数是否是候选人
////            if (numbers[i] == hou)
////            {
////                num++;
////            }
////            else {
////                num--;
////            }
////        }
////    }
////    return hou;
////}
////};
////
////
//////DP4 最小花费爬楼梯
//////给定一个整数数组cost  ，其中cost[i]  是从楼梯第 i 个台阶向上爬需要支付的费用，下标从0开始。
//////一旦你支付此费用，即可选择向上爬一个或者两个台阶。
//////你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
//////请你计算并返回达到楼梯顶部的最低花费。
////#include <iostream>
////using namespace std;
////
////int main() {
////    int n;
////    scanf("%d", &n);
////    int arr[n];
////    for (int i = 0; i < n; i++)
////    {
////        scanf("%d", &arr[i]);
////    }
////    int cost = 0;
////    if (n == 1)
////    {
////        printf("%d", arr[0]);
////        return 0;
////    }
////    if (n == 2)
////    {
////        cost = arr[0] < arr[1] ? arr[0] : arr[1];
////        printf("%d", cost);
////        return 0;
////    }
////    int cost_left = 0;
////    int cost_right = 0;
////    int left = -1;
////    while (left + 2 < n)
////    {
////        if (arr[left + 1] < arr[left + 2])
////        {
////            cost_left += arr[left + 1];
////            left++;
////        }
////        else {
////            cost_left += arr[left + 2];
////            left += 2;
////        }
////    }
////    // printf("%d",cost_left);
////
////    int right = n;
////    while (right - 2 >= 0)
////    {
////        if (arr[right - 1] < arr[right - 2])
////        {
////            cost_right += arr[right - 1];
////            right--;
////        }
////        else {
////            cost_right += arr[right - 2];
////            right -= 2;
////        }
////    }
////    // printf("%d",cost_right);
////    if (cost_left < cost_right)
////        printf("%d", cost_left);
////    else
////        printf("%d", cost_right);
////}
////
//
//
//
////单词搜索
//class Solution1 {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param board string字符串vector
//     * @param word string字符串
//     * @return bool布尔型
//     */
//    bool exist_e(vector<string>& brr, string word, int i, int j)
//    {
//        int k = 0;
//        while (k < word.size())
//        {
//            if (brr[i][j] == word[k])
//            {
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i - 1][j - 1] == word[k])
//            {
//                i = i - 1;
//                j = j - 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i - 1][j] == word[k])
//            {
//                i = i - 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i - 1][j + 1] == word[k])
//            {
//                i = i - 1;
//                j = j + 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i][j - 1] == word[k])
//            {
//                j = j - 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i][j + 1] == word[k])
//            {
//                j = j + 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i + 1][j - 1] == word[k])
//            {
//                i = i + 1;
//                j = j - 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i + 1][j] == word[k])
//            {
//                i = i + 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else if (brr[i + 1][j + 1] == word[k])
//            {
//                i = i + 1;
//                j = j + 1;
//                brr[i][j] = '1';
//                k++;
//            }
//            else {
//                return false;
//            }
//        }
//        return true;
//    }
//    bool exist(vector<string>& board, string word) {
//        // write code here
//        vector<string> brr;
//        brr.resize(board.size() + 2);
//        for (int i = 0; i < brr.size(); i++)
//        {
//            brr[i].resize(board[0].size() + 2);
//            for (int j = 0; j < brr[i].size(); j++)
//            {
//                if (i == 0 || i == brr.size() - 1 || j == 0 || j == brr[i].size() - 1)
//                {
//                    brr[i][j] = '0';
//                }
//                else {
//                    brr[i][j] = board[i - 1][j - 1];
//                }
//            }
//        }
//        for (int i = 0; i < brr.size(); i++)
//        {
//            for (int j = 0; j < brr[i].size(); j++)
//            {
//                if (brr[i][j] == word[0])
//                {
//                    if (exist_e(brr, word, i, j))
//                    {
//                        return true;
//                    }
//                }
//                //printf("%c ",brr[i][j]);
//            }
//            //printf("\n");
//        }
//        //cout<<word<<endl;
//        return false;
//    }
//};
//
////int main()
////{
////
////    Solution1 s;
////    return 0;
////}
//
//
//
//
//
//////大数乘法
////class Solution {
////public:
////    /**
////     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
////     *
////     *
////     * @param s string字符串 第一个整数
////     * @param t string字符串 第二个整数
////     * @return string字符串
////     */
////
////    string solve_add(string s, string t) {
////        // write code here
////        if (t.empty())
////            return s;
////        if (s.empty())
////            return t;
////        int i = s.size() - 1, j = t.size() - 1;;
////        int c = 0, s1 = 0;
////        string ret;
////        while (i >= 0 || j >= 0)
////        {
////            if (i >= 0 && j >= 0)
////            {
////                s1 = (s[i] - '0') + (t[j] - '0') + c;
////                //printf("S%d\n",s1);
////                c = s1 / 10;
////                s1 %= 10;
////                //printf("c%d s%d\n",c,s1);
////                ret += s1 + '0';
////                i--; j--;
////            }
////            else if (i >= 0 && j < 0)
////            {
////                s1 = (s[i] - '0') + c;
////                c = s1 / 10;
////                s1 = s1 % 10;
////                ret += s1 + '0';
////                i--;
////            }
////            else {
////                s1 = (t[j] - '0') + c;
////                c = s1 / 10;
////                s1 = s1 % 10;
////                char tmp = s1 + '0';
////                ret += tmp;
////                j--;
////            }
////        }
////        if (c != 0)
////            ret += c + '0';
////
////        reverse(ret.begin(), ret.end());
////        return ret;
////    }
////
////    string solve(string s, string t) {
////        // write code here
////        if (t == "0")
////            return t;
////        if (s == "0")
////            return s;
////        int i = s.size() - 1, j = t.size() - 1;
////        string ret;
////        for (i = s.size() - 1; i >= 0; i--)
////        {
////            int c = 0, s1 = 0;
////            string tmp;
////            int k = i;
////            while (k < s.size() - 1)
////            {
////                tmp += '0';
////                k++;
////            }
////            for (j = t.size() - 1; j >= 0; j--)
////            {
////                s1 = (s[i] - '0') * (t[j] - '0') + c;
////                c = s1 / 10;
////                s1 %= 10;
////                tmp += s1 + '0';
////            }
////            if (c != 0)
////                tmp += c + '0';
////            reverse(tmp.begin(), tmp.end());
////
////            printf("tmp %s\n", tmp.c_str());
////            ret = solve_add(ret, tmp);
////        }
////
////        return ret;
////
////    }
////};
////
////
////
//////大数加法
////
////class Solution {
////public:
////    /**
////     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
////     *
////     * 计算两个数之和
////     * @param s string字符串 表示第一个整数
////     * @param t string字符串 表示第二个整数
////     * @return string字符串
////     */
////    string solve(string s, string t) {
////        // write code here
////        if (t.empty())
////            return s;
////        if (s.empty())
////            return t;
////        int i = s.size() - 1, j = t.size() - 1;;
////        int c = 0, s1 = 0;
////        string ret;
////        while (i >= 0 || j >= 0)
////        {
////            if (i >= 0 && j >= 0)
////            {
////                s1 = (s[i] - '0') + (t[j] - '0') + c;
////                //printf("S%d\n",s1);
////                c = s1 / 10;
////                s1 %= 10;
////                //printf("c%d s%d\n",c,s1);
////                ret += s1 + '0';
////                i--; j--;
////            }
////            else if (i >= 0 && j < 0)
////            {
////                s1 = (s[i] - '0') + c;
////                c = s1 / 10;
////                s1 = s1 % 10;
////                ret += s1 + '0';
////                i--;
////            }
////            else {
////                s1 = (t[j] - '0') + c;
////                c = s1 / 10;
////                s1 = s1 % 10;
////                char tmp = s1 + '0';
////                ret += tmp;
////                j--;
////            }
////        }
////        if (c != 0)
////            ret += c + '0';
////
////        reverse(ret.begin(), ret.end());
////        return ret;
////    }
////};
//
//
//////链表相加
////
//// struct ListNode {
//// int val;
//// struct ListNode *next;
//// ListNode(int x) : val(x), next(nullptr) {}
//// };
//// 
////    class Solution {
////    public:
////        /**
////         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
////         *
////         *
////         * @param head1 ListNode类
////         * @param head2 ListNode类
////         * @return ListNode类
////         */
////        void reverse_list(ListNode*& head)
////        {
////            int n = 0;
////            ListNode* len = head;
////            while (len != nullptr)
////            {
////                n++;
////                len = len->next;
////            }
////            int arr[100];
////            ListNode* tmp = head;
////            for (int i = 0; i < n; i++)
////            {
////                arr[i] = tmp->val;
////                tmp = tmp->next;
////            }
////            ListNode* ret = head;
////            int i = n - 1;
////            while (i >= 0)
////            {
////                ret->val = arr[i];
////                ret = ret->next;
////                i--;
////            }
////        }
////        // void Pushback(ListNode*& head,int s)
////        // {
////        //     ListNode* tmp=new ListNode(s);
////        //     tmp->next=nullptr;
////        //     if(head==nullptr)
////        //     {
////        //         head=tmp;
////        //         return ;
////        //     }
////        //     ListNode* ret=head;
////        //     while(ret->next!=nullptr)
////        //     {
////        //         ret=ret->next;
////        //     }
////        //     ret->next=tmp;
////        // }
////        void pushtop(ListNode*& head, int s)
////        {
////            ListNode* tmp = new ListNode(s);
////            tmp->next = head;
////            head = tmp;
////        }
////        ListNode* addInList(ListNode* head1, ListNode* head2) {
////            // write code here
////            if (head1 == nullptr)
////                return head2;
////            if (head2 == nullptr)
////                return head1;
////            reverse_list(head1);
////            reverse_list(head2);
////            ListNode* ret = nullptr;
////            int c = 0, s = 0;
////            ListNode* h = head2;
////            // while(h!=nullptr)
////            // {
////            //     printf("%d ",h->val);
////            //     h=h->next;
////            // }
////            while (head1 != nullptr || head2 != nullptr)
////            {
////                if (head1 != nullptr && head2 != nullptr)
////                {
////                    s = head1->val + head2->val + c;
////                    c = s / 10;
////                    s %= 10;
////                    pushtop(ret, s);
////                    head1 = head1->next;
////                    head2 = head2->next;
////                    //printf("C%d\n",c);
////                }
////                else if (head1 != nullptr && head2 == nullptr)
////                {
////                    s = head1->val + c;
////                    c = s / 10;
////                    s %= 10;
////                    pushtop(ret, s);
////                    head1 = head1->next;
////                    //printf("C%d\n",c);
////                }
////                else {
////                    s = head2->val + c;
////                    c = s / 10;
////                    s %= 10;
////                    pushtop(ret, s);
////                    head2 = head2->next;
////                    //printf("C%d\n",c);
////                }
////            }
////            if (c != 0)
////                pushtop(ret, c);
////            return ret;
////        }
////};
//
//
//
//
////牛客点击消除
//#include <cstdio>
//#include <iostream>
//#include <string>
//
//using namespace std;
//
//int main()
//{
//    //char arr[300010];
//    //scanf("%s", arr);
//    //string s1;
//    //s1 += arr[0];
//    //int i = 1;
//    //while (arr[i] != '\0')
//    //{
//    //    if (s1[s1.size() - 1] != arr[i])
//    //    {
//    //        s1.push_back(arr[i]);
//    //    }
//    //    else {
//    //        s1.pop_back();
//    //    }
//    //    i++;
//    //}
//    //if (s1 == "")
//    //    cout << 0 << endl;
//    //cout << s1 << endl;
//
//    vector<int> arr;
//    
//    return 0;
//}
//
//
//
//
////动态规划
////1137. 第 N 个泰波那契数
////泰波那契序列 Tn 定义如下：
////T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn + 3 = Tn + Tn + 1 + Tn + 2
////给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
//class Solution4 {
//public:
//    int tribonacci(int n) {
//        if (n == 0)
//            return 0;
//        if (n == 1 || n == 2)
//            return 1;
//
//        int dp[100];
//        dp[0] = 0;
//        dp[1] = 1;
//        dp[2] = 1;
//        for (int i = 3; i <= n; i++)
//        {
//            dp[i] = dp[i - 3] + dp[i - 2] + dp[i - 1];
//        }
//        return dp[n];
//    }
//};
////空间优化后
//class Solution5 {
//public:
//    int tribonacci(int n) {
//        if (n == 0)
//            return 0;
//        if (n == 1)
//            return 1;
//        if (n == 2)
//            return 1;
//        if (n == 3)
//            return 2;
//        int a = 0;
//        int b = 1;
//        int c = 1;
//        int d = a + b + c;
//        while (n - 4 >= 0)
//        {
//            a = b;
//            b = c;
//            c = d;
//            d = a + b + c;
//            n--;
//        }
//        return d;
//    }
//};
//
//
//
////动态规划
////最小花费爬楼梯
//#include <cstddef>
//#include <iostream>
//using namespace std;
//int Min_di(int a, int b)
//{
//    return a < b ? a : b;
//}
//int main()
//{
//    int n;
//    cin >> n;
//    int cost[10000];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> cost[i];
//    }
//    int di[10005] = { 0 };
//    di[0] = 1;
//    di[1] = 1;
//    for (int i = 2; i <= n; i++)
//    {
//        di[i] = Min_di(di[i - 1] * cost[i - 1], di[i - 2] * cost[i - 2]);
//    }
//    for (int i = 0; i < n; i++)
//        printf("%d ", di[i]);
//    printf("\n");
//    printf("%d", di[n - 1]);
//    return 0;
//}
//
//
//
//
//
//
//
////最大公倍数
////最大公倍数为两数相乘除以最大公约数
//#include <iostream>
//using namespace std;
//
//int main() {
//    int a, b;
//    cin >> a >> b;
//    int a1 = a, b1 = b;
//    int c = a1 % b1;
//    while (c)
//    {
//        a1 = b1;
//        b1 = c;
//        c = a1 % b1;
//    }
//    int d = a * b / b1;
//    printf("%d", d);
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////数组中的最长连续子序列
///**
// * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
// *
// * max increasing subsequence
// * @param arr int整型一维数组 the array
// * @param arrLen int arr数组长度
// * @return int整型
// */
//int compar(const void* e1, const void* e2)
//{
//    return *(int*)e1 - *(int*)e2;
//}
//#include <stdlib.h>
//int MLS(int* arr, int arrLen) {
//    // write code here
//    qsort(arr, arrLen, sizeof(int), compar);
//    // for(int i=0;i<arrLen;i++)
//    // {
//    //     printf("%d ",arr[i]);
//    // }
//    int len = 1; int i = 0;
//    while (i + 1 < arrLen)
//    {
//        if (arr[i] + 1 == arr[i + 1])
//        {
//            int j = i;
//            int tmp_len = 1;
//            while (arr[j] + 1 == arr[j + 1] && j + 1 < arrLen)
//            {
//                tmp_len++;
//                j++;
//            }
//            if (tmp_len > len)
//                len = tmp_len;
//            i = j;
//        }
//        i++;
//    }
//    return len;
//}
//
//
//
//
//#include <algorithm>
//#include <iostream>
//#include <string>
//
//
////添加逗号
//using namespace std;
//
//int main() {
//    long long a;
//    cin >> a;
//    string s;
//    int t = 0;
//    while (a)
//    {
//        s += a % 10 + '0';
//        a /= 10;
//        t++;
//        if (t % 3 == 0 && a != 0)
//            s += ',';
//    }
//    reverse(s.begin(), s.end());
//    cout << s << endl;
//    return 0;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////跳台阶
//#include <iostream>
//using namespace std;
//
//int main() {
//    int a;
//    cin >> a;
//    if (a == 1)
//        cout << 1 << endl;
//    else if (a == 2)
//        cout << 2 << endl;
//    else
//    {
//        int b = 1, c = 2;
//        int d = b + c;
//        for (int i = 3; i < a; i++)
//        {
//            b = c;
//            c = d;
//            d = b + c;
//        }
//        cout << d << endl;
//    };
//    return 0;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
////扑克牌顺子
///**
// * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
// *
// *
// * @param numbers int整型一维数组
// * @param numbersLen int numbers数组长度
// * @return bool布尔型
// */
//#include <math.h>
//#include <stdbool.h>
//int compar(void* e1, void* e2)
//{
//    return *(int*)e1 - *(int*)e2;
//}
//
//#include <stdlib.h>
//bool IsContinuous(int* numbers, int numbersLen) {
//    // write code here
//    qsort(numbers, numbersLen, sizeof(int), compar);
//    // for(int i=0;i<numbersLen;i++)
//    // {
//    //     printf("%d ",numbers[i]);
//    // }
//    int i = 0;
//    int num_0 = 0;
//    while (i + 1 < numbersLen) {
//        if (numbers[i] == 0)
//        {
//            num_0++;
//            i++;
//        }
//        else {
//            if (numbers[i] == numbers[i + 1])
//                return false;
//            //printf("%d\n",num_0);
//            if (numbers[i] + 1 == numbers[i + 1])
//            {
//                i++;
//            }
//            else {
//                int tmp = numbers[i + 1] - numbers[i] - 1;
//                if (tmp > num_0)
//                    return false;
//                num_0 -= tmp;
//                i++;
//            }
//        }
//    }
//    return true;;
//}
//
//
//
//
//
////最长回文子串
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param A string字符串
//     * @return int整型
//     */
//    int getLongestPalindrome(string A) {
//        // write code here
//        if (A.size() == 1)
//            return 1;
//        int num = 0;
//        int j = A.size() - 1;
//        for (int i = 0; i + 1 < A.size(); i++)
//        {
//            j = A.size() - 1;
//            while (A[j] != A[i])
//            {
//                j--;
//            }
//            if (i == j)
//                continue;
//            //cout<<j;
//            int i1 = i, j1 = j;
//            int tmp = 0;
//            if ((j1 - i1 + 1) % 2 == 0)
//            {
//                while (i1 <= j1)
//                {
//                    if (A[i1] == A[j1])
//                    {
//                        tmp += 2;
//                        i1++; j1--;
//                    }
//                    else {
//                        tmp = 0;
//                        break;
//                    }
//                }
//            }
//            else {
//                tmp++;
//                while (i1 < j1)
//                {
//                    if (A[i1] == A[j1])
//                    {
//                        tmp += 2;
//                        i1++; j1--;
//                    }
//                    else {
//                        tmp = 0;
//                        break;
//                    }
//                }
//            }
//            num = num > tmp ? num : tmp;
//        }
//        return num;
//    }
//};
//
//
//
////买股票的最好时机
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int arr[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//        //cout<<arr[i]<<' ';
//    }
//    int max = 0;
//    //int tmp;
//    for (int i = 0; i < n; i++)
//    {
//        int tmp;
//        for (int j = i + 1; j < n; j++)
//        {
//            tmp = arr[j] - arr[i];
//            if (tmp > max)
//            {
//                max = tmp;
//            }
//        }
//    }
//    cout << max << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////河过卒
//#include <cstdlib>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int num_way(vector<vector<int>>& v, int i, int j)
//{
//    int num = 0;
//    if (j + 1 < v[i].size() && v[i][j + 1] != 1)
//    {
//        num = num_way(v, i, j + 1);
//    }
//    if (i + 1 < v.size() && v[i + 1][j] != 1)
//    {
//        num = num_way(v, i + 1, j);
//    }
//    else
//    {
//        if (i == v.size() - 1 && j == v[i].size() - 1)
//            return num + 1;
//        return num;
//    }
//    return num;
//}
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int x, y;
//    cin >> x >> y;
//    vector<vector<int>> v;
//    n++; m++;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        v[i].resize(m);
//        for (int j = 0; j < m; j++)
//            v[i][j] = 0;
//    }
//    //cout<<n<<m<<x<<y<<endl;
//    v[x][y] = 1;
//    for (int x1 = 0; x1 < n; x1++)
//    {
//        for (int y1 = 0; y1 < m; y1++)
//        {
//            if ((int)abs(x1 - x) + (int)abs(y1 - y) == 3 && x1 != x && y1 != y)
//                v[x1][y1] = 1;
//        }
//    }
//    int num = num_way(v, 0, 0);
//    cout << num << endl;
//    // for(int x1=0;x1<n;x1++)
//    // {
//    //     for(int y1=0;y1<m;y1++)
//    //     {c
//    //         cout<<v[x1][y1]<<' ';
//    //     }
//    //     cout<<endl;
//    // }
//    //while();
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
////水果大礼包
//
//
//
////#include <asm-generic/errno.h>
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n, m, a, b;
//    long long sum = 0;
//    long long sum1 = 0;
//    long long sum2 = 0;
//    cin >> n >> m >> a >> b;
//    int n1 = n, m1 = m;
//    while (n1 >= 2 && m1 >= 1)
//    {
//        n1 -= 2;
//        m1--;
//        sum1 += a;
//    }
//    if (n1 == 1 && m1 >= 2)
//        sum1 += b;
//
//    int n2 = n, m2 = m;
//    while (m2 >= 2 && n2 >= 1)
//    {
//        m2 -= 2;
//        n2--;
//        sum2 += b;
//    }
//    if (m2 == 1 && n2 >= 2)
//        sum2 += a;
//    sum = sum1 > sum2 ? sum1 : sum2;
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//// 
//// 
//// 
////买卖股票的最好时机
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int arr[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    int i = 0, j = 1;
//    int sum = 0;
//    while (i < n && j < n)
//    {
//        if (arr[j] < arr[j + 1])
//        {
//            j++;
//        }
//        else {
//            sum += arr[j] - arr[i] > 0 ? arr[j] - arr[i] : 0;
//            j++;
//            i = j;
//            //cout<<sum<<' '<<i<<j<<endl;
//        }
//        //cout<<sum;
//    }
//    if (i == 0)
//        sum += arr[j - 1] - arr[i] > 0 ? arr[j - 1] - arr[i] : 0;
//    cout << sum << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<arr[i];
//    // }
//}
//// 64 位输出请用 printf("%lld")
//// 
//// 
//// 
////倒置字符串
//#include <algorithm>
//#include <cstdio>
//#include <iostream>
//using namespace std;
//#include <string>
//
//int main() {
//    string s;
//    char ch = getchar();
//    while (ch != '\n')
//    {
//        s += ch;
//        ch = getchar();
//    }
//    //cin>>s;
//    //cout<<s;
//    reverse(s.begin(), s.end());
//    //int num=0;
//    string::iterator t1 = s.begin();
//    string::iterator t2 = s.begin();
//    while (t1 < s.end())
//    {
//        if (*t1 != ' ')
//        {
//            t1++;
//        }
//        else {
//            reverse(t2, t1);
//            t2 = t1 + 1;
//            t1 = t2;
//        }
//
//    }
//    reverse(t2, t1);
//    cout << s;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////删除公共字符
//#include <cstdio>
//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    string s1;
//    string s2;
//    char ch = getchar();
//    while (ch != '\n')
//    {
//        s1 += ch;
//        ch = getchar();
//    }
//    ch = getchar();
//    while (ch != '\n')
//    {
//        s2 += ch;
//        ch = getchar();
//    }
//    string::iterator t1 = s1.begin();
//    while (t1 != s1.end())
//    {
//        bool flag = false;
//        string::iterator t2 = s2.begin();
//        while (t2 != s2.end())
//        {
//            if (*t1 == *t2)
//            {
//                s1.erase(t1);
//                flag = true;
//                break;
//            }
//            t2++;
//        }
//        if (flag == true)
//            continue;
//        t1++;
//    }
//    cout << s1 << endl;
//    //cout<<s2<<endl;
//}
//// 64 位输出请用 printf("%lld")
//// 
//// 
//// 
//// 
//// 
////两个链表的第一个公共节点
//struct ListNode {
//    int val;
//    struct ListNode *next;
//};
//class Solution {
//public:
//    ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
//        ListNode* ret = nullptr;
//        int n1 = 0, n2 = 0;
//        ListNode* tmp1 = pHead1;
//        while (tmp1 != nullptr)
//        {
//            n1++;
//            tmp1 = tmp1->next;
//        }
//        ListNode* tmp2 = pHead2;
//        while (tmp2 != nullptr)
//        {
//            n2++;
//            tmp2 = tmp2->next;
//        }
//
//        if (n1 > n2)
//        {
//            while (n1 != n2)
//            {
//                pHead1 = pHead1->next;
//                n1--;
//            }
//        }
//        else {
//            while (n1 != n2)
//            {
//                pHead2 = pHead2->next;
//                n2--;
//            }
//        }
//
//        while (pHead1 != nullptr && pHead2 != nullptr)
//        {
//            if (pHead1 == pHead2)
//            {
//                ret = pHead1;
//                break;
//            }
//            pHead1 = pHead1->next;
//            pHead2 = pHead2->next;
//        }
//        return ret;
//    }
//};
//
//
//
//
//
////Mair和shiny
//#include <cstdio>
//#include <iostream>
//using namespace std;
//
//int arr[200];
//int main() {
//    int n;
//    cin >> n;
//    string s;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> s;
//    }
//    int sum = 0;
//    int i = 0;
//    string ret;
//    while (i < n)
//    {
//        if (s[i] == 's')
//        {
//            int n = 0;
//            int k = i;
//            while (s[i] == 's')
//            {
//                ret += s[i];
//                i++;
//                n++;
//            }
//            if (s[i] == 'h')
//            {
//                while (s[i] == 'h')
//                {
//                    ret += s[i];
//                    i++;
//                    n++;
//                }
//                if (s[i] == 'y')
//                {
//                    while (s[i] == 'y')
//                    {
//                        ret += s[i];
//                        i++;
//                        n++;
//                    }
//                }
//                else {
//                    ret.erase(k, n);
//
//                }
//            }
//            else {
//                ret.erase(k, n);
//            }
//        }
//        i++;
//    }
//        cout << ret << endl;
//    i = 0;
//    while (ret[i] != '\0')
//    {
//        arr[ret[i]]++;
//        i++;
//    }
//    // int sum=0;
//    // string s2="shiny";
//    sum = arr['s'] * arr['h'] * arr['y'];
//    // //sum-=arr['n']*arr['i'];
//    // //cout<<arr['n']<<endl;
//    // //cout<<arr['i']<<endl;
//    // int i=0,j=0;
//    // while(i<n)
//    // {
//    //     if(s[i]=='s')
//    //     {
//    //         bool flag=false;
//    //         int j=0;
//    //         int k=i;
//    //         while(j<5)
//    //         {
//    //             if(s[k]==s2[j])
//    //             {
//    //                 k++;j++;
//    //             }
//    //             else {
//    //                 flag=true;
//    //                 break;
//    //             }
//    //         }
//    //         if(flag==false)
//    //         {
//    //             sum--;
//    //         }
//    //     }
//    //     i++;
//    // }
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
////牛牛冲钻5
//#include <cstdio>
//#include <iostream>
//using namespace std;
//
//int main() {
//    int t;
//    cin >> t;
//    while (t)
//    {
//        int n, k;
//        cin >> n >> k;
//        getchar();
//        char ch = getchar();
//        string s;
//        while (ch != '\n')
//        {
//            s += ch;
//            ch = getchar();
//        }
//        //cout<<n<<k<<s<<endl;
//        int i = 0;
//        int sum = 0;
//        int time = 0;
//        while (i < n)
//        {
//            if (s[i] == 'W')
//            {
//                time++;
//                if (time >= 3)
//                    sum += k;
//                else
//                    sum += 1;
//            }
//            else {
//                time = 0;
//                sum--;
//            }
//            i++;
//        }
//        cout << sum << endl;
//        t--;
//    }
//}
////// 64 位输出请用 printf("%lld")
//////最长无重复子数组
////class Solution {
////public:
////        /**
////         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
////         *
////         *
////         * @param arr int整型vector the array
////         * @return int整型
////         */
////    bool Ishave(vector<int> arr, int n)
////    {
////        for (int i = 0; i < arr.size(); i++)
////        {
////            if (arr[i] == n)
////                return false;
////        }
////        return true;
////    }
////    int maxLength(vector<int>& arr) {
////        // write code here
////        int i = 0;
////        int max = 0;
////        while (i < arr.size())
////        {
////            int j = i;
////            vector<int> brr;
////            while (j < arr.size())
////            {
////                if (Ishave((brr), arr[j]))
////                {
////                    brr.push_back(arr[j]);
////                }
////                else
////                    break;
////                j++;
////            }
////            max = brr.size() > max ? brr.size() : max;
////            i++;
////        }
////        return max;
////    }
////};
////重排字符串
//#include <cstdio>
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    getchar();
//    string s;
//    char ch = getchar();
//    while (ch != '\n')
//    {
//        s += ch;
//        ch = getchar();
//    }
//    int arr[200] = { 0 };
//    for (int i = 0; i < s.size(); i++)
//    {
//        arr[s[i]]++;
//    }
//    // int Size=0;
//    // if(s.size()%2==0)
//    // {
//    //     Size=s.size()/2;
//    // }
//    // else {
//    //     Size=s.size()/2+1;
//    // }
//    // for(int i=0;i<200;i++)
//    // {
//    //     if(arr[i]>Size)
//    //     {
//    //        cout<<"no"<<endl; 
//    //        return 0;
//    //     }
//    // }
//    int max = 0;
//    int max_i = 0;
//    for (int i = 0; i < 200; i++)
//    {
//        if (arr[i] > max)
//        {
//            max = arr[i];
//            max_i = i;
//        }
//    }
//
//    string s1;
//    string s2;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] != max_i)
//        {
//            s1 += s[i];
//        }
//        else {
//            s2 += s[i];
//        }
//    }
//    //cout<<s1<<endl;
//    //cout<<s2<<endl;
//    if (s1.size() - s2.size() == 1 || s2.size() - s1.size() == 1)
//    {
//        cout << "yes" << endl;
//        int i = 0;
//        string ret;
//        if (s1.size() > s2.size())
//        {
//            while (i < s2.size())
//            {
//                ret += s1[i];
//                ret += s2[i];
//                i++;
//            }
//            ret += s1[i];
//        }
//        else {
//            while (i < s1.size())
//            {
//                ret += s2[i];
//                ret += s1[i];
//                i++;
//            }
//            ret += s2[i];
//        }
//        cout << ret << endl;
//        return 0;
//    }
//    else {
//        cout << "no" << endl;
//        return 0;
//    }
//    // cout<<"yes"<<endl;
//    // int i=0;
//    // string ret;
//    // if(s1.size()>s2.size())
//    // {
//    //     while(i<s2.size())
//    //     {
//    //         ret+=s1[i];
//    //         ret+=s2[i];
//    //         i++;
//    //     }
//    //     ret+=s1[i];
//    // }
//    // else {
//    //     while(i<s1.size())
//    //     {
//    //         ret+=s2[i];
//    //         ret+=s1[i];
//    //         i++;
//    //     }
//    //     ret+=s2[i];
//    // }
//    // cout<<ret<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
////乒乓球框
//#include <cstdio>
//#include <iostream>
//using namespace std;
//long long arr1[200] = { 0 };
//long long arr2[200] = { 0 };
//
//int main() {
//    char ch = getchar();
//    string s1;
//    while (ch != '\n')
//    {
//        s1 += ch;
//        ch = getchar();
//    }
//    string s2;
//    ch = getchar();
//    while (ch != '\n')
//    {
//        s2 += ch;
//        ch = getchar();
//    }
//    for (int i = 0; i < s1.size(); i++)
//    {
//        arr1[s1[i]]++;
//    }
//    for (int i = 0; i < s2.size(); i++)
//    {
//        arr2[s2[i]]++;
//    }
//    for (int i = 0; i < 150; i++)
//    {
//        if (arr2[i] != 0)
//        {
//            arr1[i] -= arr2[i];
//            if (arr1[i] < 0)
//            {
//                cout << "No" << endl;
//                return 0;
//            }
//        }
//    }
//    cout << "Yes" << endl;
//    // cout<<s1<<endl;
//    // cout<<s2<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
////组队竞赛
//#include <algorithm>
//#include <cstdlib>
//#include <iostream>
//#include <vector>
//#include <math.h>
//using namespace std;
//// int compar(void* e1,void*e2)
//// {
////     return *(int*)e1-*(int*)e2;
//// }
//int main()
//{
//    int n;
//    cin >> n;
//    vector<int> v;
//    //int arr[3*n];
//    int a;
//    //size_t num=0;
//    for (int i = 0; i < 3 * n; i++)
//    {
//        cin >> a;
//        v.push_back(a);
//        //num++;
//    }
//    // for(int i=0;i<v.size();i++)
//    // {
//    //     cout<<v[i]<<' ';
//    // }
//    // cout<<endl;
//    sort(v.begin(), v.end());
//    //qsort(arr, sizeof(int), num, compar);
//    vector<vector<int>> vv1;
//    vv1.resize(n);
//    for (int i = 0; i < n; i++)
//        vv1[i].resize(3);
//    int i = 0, j = 0, k = 0;
//    while (k < v.size())
//    {
//        if (i < n)
//        {
//            vv1[i][j] = v[k++];
//            i++;
//        }
//        else {
//            i = 0; j++;
//        }
//    }
//    int sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        sum += vv1[i][1];
//    }
//    // for(int i=0;i<v.size();i++)
//    // {
//    //     cout<<v[i]<<' ';
//    // }
//    // cout<<endl;
//    cout << sum << endl;
//    return 0;
//}
//
////删除相邻数字的最大分数
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int a;
//    vector<int> v;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> a;
//        v.push_back(a);
//    }
//    sort(v.begin(), v.end());
//    vector<int> v1 = v;
//
//    int sum1 = 0;
//    while (!v.empty())
//    {
//        sum1 += *(v.end() - 1);
//        int tmp = *(v.end() - 1);
//        vector<int>::iterator it = v.begin();
//        while (it != v.end())
//        {
//            if (*it == tmp - 1 || *it == tmp + 1)
//                it = v.erase(it);
//            else
//            {
//                it++;
//            }
//        }
//        v.erase(v.end() - 1);
//    }
//    //cout<<sum1<<endl;
//    int m = 0;
//    int max_num = 0;
//    int max_tmp = 1;
//    int i = 0;
//    while (i + 1 < v1.size())
//    {
//        if (v1[i] == v1[i + 1])
//        {
//            max_tmp++;
//            i++;
//        }
//        else {
//            if (max_num < max_tmp)
//            {
//                max_num = max_tmp;
//                m = v1[i];
//            }
//            max_tmp = 1;
//            i++;
//        }
//    }
//    //cout<<m<<endl;
//    // int sum2=0;
//    // while(!v1.empty())
//    // {
//    //     sum1+=m;
//    //     int tmp=*(v.end()-1);
//    //     vector<int>::iterator it=v.begin();
//    //     while(it!=v.end())
//    //     {
//    //         if(*it==tmp-1||*it==tmp+1)
//    //             it=v.erase(it);
//    //         else
//    //         {
//    //             it++;
//    //         }
//    //     }
//    //     v.erase(v.end()-1);
//    // }
//    // for(int i=0;i<n;i++)
//    // cout<<v1[i];
//    // cout<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
////面试题 08.01.三步问题
////三步问题。有个小孩正在上楼梯，楼梯有n阶台阶，小孩一次可以上1阶、2阶或3阶。
////实现一种方法，计算小孩有多少种上楼梯的方式。结果可能很大，你需要对结果模1000000007。
//class Solution {
//public:
//    int waysToStep(int n) {
//        int dp[1000000] = { 0 };
//        dp[0] = 1;
//        dp[1] = 2;
//        dp[2] = 4;
//        if (n == 1)
//            return dp[0];
//        if (n == 2)
//            return dp[1];
//        if (n == 3)
//            return dp[2];
//        for (int i = 3; i < n; i++)
//        {
//            //每做一次加法运算都可能超题目范围，所以要模2次
//            dp[i] = ((dp[i - 3] + dp[i - 2]) % 1000000007 + dp[i - 1]) % 1000000007;
//        }
//        return dp[n - 1];
//    }
//};
//
//
//
////LCR 088. 使用最小花费爬楼梯
////数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
////每当爬上一个阶梯都要花费对应的体力值，一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
////请找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
//class Solution {
//public:
//    int minCostClimbingStairs(vector<int>& cost) {
//        vector<int> dp(cost.size() + 1);
//        dp[0] = 0;
//        dp[1] = 0;
//        if (cost.size() < 2)
//        {
//            return 0;
//        }
//        for (int i = 2; i < dp.size(); i++)
//        {
//            //dp 表示，到i位置的最小花费
//            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
//        }
//        return *(dp.end() - 1);
//    }
//};
//
//
//
//
//
////平方数
//#include <iostream>
//#include <algorithm>
//#include <math.h>
//using namespace std;
//
//int main() {
//    long long a;
//    cin >> a;
//    long long b = sqrtf(a);
//    long long t1 = b * b;
//    b++;
//    long long t2 = b * b;
//    if (abs(a - t1) < abs(a - t2))
//    {
//        cout << t1 << endl;
//    }
//    else {
//        cout << t2 << endl;
//    }
//    //cout<<b<<endl;
//}
//// 64 位输出请用 printf("%lld")
////小易的升级之路
//#include <iostream>
//using namespace std;
//int getMax(int a, int b)
//{
//    int c = a % b;
//    while (c != 0)
//    {
//        a = b;
//        b = c;
//        c = a % b;
//    }
//    return b;
//}
//int main() {
//    long long a, b;
//    cin >> a >> b;
//    int arr[a];
//    for (int i = 0; i < a; i++)
//    {
//        cin >> arr[i];
//    }
//    // for(int i=0;i<a;i++)
//    // {
//    //     cout>>arr[i];
//    // }
//    for (int i = 0; i < a; i++)
//    {
//        if (b >= arr[i])
//        {
//            b += arr[i];
//        }
//        else {
//            b += getMax(arr[i], b);
//        }
//    }
//    cout << b << endl;
//}
//// 64 位输出请用 printf("%lld")
////礼物的最大值
//#include <cmath>
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param grid int整型vector<vector<>>
//         * @return int整型
//         */
//    int maxValue(vector<vector<int> >& grid) {
//        // write code here
//        int n = grid.size();
//        int m = grid[0].size();
//        vector<vector<int>> di;
//        di.resize(n);
//        for (int i = 0; i < n; i++)
//        {
//            di[i].resize(m);
//            for (int j = 0; j < m; j++)
//            {
//                di[i][j] = 0;
//            }
//        }
//        // for(int i=0;i<n;i++)
//        // {
//        //     for(int j=0;j<m;j++)
//        //     {
//        //         cout<<di[i][j]<<' ';
//        //     }
//        //     cout<<endl;
//        // }
//
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < m; j++)
//            {
//                if (i - 1 >= 0 && j - 1 >= 0)
//                {
//                    di[i][j] = max(di[i - 1][j] + grid[i - 1][j], di[i][j - 1] + grid[i][j - 1]);
//                }
//                else if (i - 1 >= 0)
//                {
//                    di[i][j] = di[i - 1][j] + grid[i - 1][j];
//                }
//                else if (j - 1 >= 0)
//                {
//                    di[i][j] = di[i][j - 1] + grid[i][j - 1];
//                }
//            }
//        }
//        return di[n - 1][m - 1] + grid[n - 1][m - 1];
//    }
//};
//
//
//
//
//
//
//
//
////day20
////经此一役小红所向无敌
//#include <iostream>
//using namespace std;
//
//int main() {
//    int a, h, b, k;
//    long long sum = 0;
//    cin >> a >> h >> b >> k;
//    int t1 = h / b;
//    int c1 = h % b;
//    if (c1 != 0)
//        t1++;
//    int t2 = k / a;
//    c1 = k % a;
//    if (c1 != 0)
//        t2++;
//    int min_t = t1 < t2 ? t1 : t2;
//    sum += min_t * (a + b);
//    h -= min_t * b;
//    k -= min_t * a;
//    //cout<<a<<h<<b<<k<<endl;
//    // while(h>0&&k>0)
//    // {
//    //     sum+=a+b;
//    //     h-=b;
//    //     k-=a;
//    // }
//    if (h > 0 && k <= 0)
//    {
//        sum += a * 10;
//    }
//    else if (h <= 0 && k > 0)
//    {
//        sum += b * 10;
//    }
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
////连续子数组最大和
//#include <iostream>
//using namespace std;
//int main() {
//    int n;
//    cin >> n;
//    long long arr[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<arr[i];
//    // }
//    long long  di[n];
//    di[0] = arr[0];
//    for (int i = 1; i < n; i++)
//    {
//        di[i] = max(arr[i], di[i - 1] + arr[i]);
//    }
//    int max = di[0];
//    for (int i = 0; i < n; i++)
//    {
//        max = max > di[i] ? max : di[i];
//    }
//    cout << max << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
////非对称之美
//#include <cstdio>
//#include <iostream>
//using namespace std;
//
//bool Ishui(string s, int i, int j)
//{
//    while (i < j)
//    {
//        if (s[i] != s[j])
//            return true;
//        i++; j--;
//    }
//    return false;
//}
//int main() {
//    char ch = getchar();
//    string s;
//    while (ch != '\n')
//    {
//        s += ch;
//        ch = getchar();
//    }
//    // if(s[0]!=s[s.size()-1])
//    // {
//    //     cout<<s.size()<<endl;
//    //     return 0;
//    // }
//    int i = 0, j = s.size() - 1;
//    int max = 0;
//    while (i < j)
//    {
//        if (Ishui(s, i, j))
//        {
//            cout << j - i + 1 << endl;
//            return 0;
//        }
//        i++; j--;
//    }
//    cout << "0" << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////day17
////小乐乐改数学
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v1;
//    int arr[9] = { 1 };
//    int t = n;
//    int i = 0;
//    while (t)
//    {
//        arr[i] = t % 10;
//        t /= 10;
//        i++;
//    }
//    for (int j = 0; j < i; j++)
//    {
//        if (arr[j] % 2 == 0)
//            arr[j] = 0;
//        else
//        {
//            arr[j] = 1;
//        }
//        v1.push_back(arr[j]);
//    }
//    reverse(v1.begin(), v1.end());
//    int j = 0;
//    while (v1[j] == 0) {
//        j++;
//    }
//    int flag = 0;
//    for (j; j < i; j++)
//    {
//        cout << v1[j];
//        flag = 1;
//    }
//    if (flag == 0)
//        cout << "0";
//
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////十字爆破
//#include <iostream>
//#include <vector>
//using namespace std;
//
//long long GetHL(vector<vector<int>> v, int i, int j)
//{
//    long long sum = 0;
//    for (int i1 = 0; i1 < v.size(); i1++)
//    {
//        sum += v[i1][j];
//    }
//    for (int j1 = 0; j1 < v[i].size(); j1++)
//    {
//        sum += v[i][j1];
//    }
//    sum -= v[i][j];
//    return sum;
//}
//int main() {
//    int n, m;
//    scanf("%d %d", &n, &m);
//    //cin>>n>>m;
//    vector<vector<int>> v;
//    v.resize(n);
//    //int t;
//    for (int i = 0; i < n; i++)
//    {
//        v[i].resize(m);
//        for (int j = 0; j < m; j++)
//        {
//            scanf("%d", &v[i][j]);
//            //cin>>v[i][j];
//        }
//    }
//    vector<vector<long long>> ret;
//    ret.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        ret[i].resize(m);
//        for (int j = 0; j < m; j++)
//        {
//            ret[i][j] = GetHL(v, i, j);
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            printf("%d ", ret[i][j]);
//        }
//        printf("\n");
//    }
//}
//// 64 位输出请用 printf("%lld")
//// 
//// 
//// 
//// 
////比那名居的桃子
//#include <iostream>
//using namespace std;
//int main() {
//    int n, k;
//    cin >> n >> k;
//    int nrr[n];
//    int krr[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> nrr[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cin >> krr[i];
//    }
//    int happy[n];
//    int shy[n];
//    happy[0] = nrr[0];
//    shy[0] = krr[0];
//    //cout<<k<<endl;
//    for (int i = 1; i < k - 1; i++)
//    {
//        int j = i;
//        happy[i] = nrr[j];
//        shy[i] = krr[j];
//        j--;
//        while (j >= 0)
//        {
//            happy[i] += nrr[j];
//            shy[i] += krr[j];
//            j--;
//        }
//        // cout<<happy[i]<<endl;
//        // cout<<shy[i]<<endl;
//    }
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<happy[i]<<' ';
//    // }
//    // cout<<endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<shy[i]<<' ';
//    // }
//    // cout<<endl;
//    for (int i = k - 1; i < n; i++)
//    {
//        happy[i] = nrr[i];
//        shy[i] = krr[i];
//        int j = i - 1;
//        int t = k - 1;
//        while (t)
//        {
//            happy[i] += nrr[j];
//            shy[i] += krr[j];
//            j--;
//            t--;
//        }
//    }
//    if (k > n)
//    {
//        cout << 1 << endl;
//        return 0;
//    }
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<happy[i]<<' ';
//    // }
//    // cout<<endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<shy[i]<<' ';
//    // }
//    // cout<<endl;
//    int max = happy[0];
//    int shy_min = shy[0];
//    int day = 0;
//    for (int i = 1; i < n; i++)
//    {
//        if (max < happy[i])
//        {
//            max = happy[i];
//            shy_min = shy[i];
//            day = i + 1;
//        }
//    }
//    //cout<<max;
//    for (int i = 1; i < n; i++)
//    {
//        if (happy[i] == max)
//        {
//            if (shy[i] <= shy_min)
//                day = i + 1;
//        }
//    }
//    cout << day - k + 1 << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
////day21
////爱丽丝的人偶
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int arr[n];
//    int j = 1;
//    int k = n;
//    for (int i = 0; i < n; i++)
//    {
//        if (i % 2 == 0)
//        {
//            arr[i] = j;
//            j++;
//        }
//        else {
//            arr[i] = k;
//            k--;
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cout << arr[i] << ' ';
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
////集合
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int a, b;
//    cin >> a >> b;
//    vector<int> arr;
//    arr.resize(a);
//    //int arr[a];
//    for (int i = 0; i < a; i++)
//    {
//        cin >> arr[i];
//    }
//    vector<int> brr;
//    brr.resize(b);
//    //int brr[a];
//    for (int i = 0; i < b; i++)
//    {
//        cin >> brr[i];
//    }
//    sort(arr.begin(), arr.end());
//    sort(brr.begin(), brr.end());
//    int i = 0, j = 0;
//    while (i < a && j < b)
//    {
//        if (arr[i] < brr[j])
//        {
//            cout << arr[i] << " ";
//            i++;
//        }
//        else if (arr[i] > brr[j])
//        {
//            cout << brr[j] << " ";
//            j++;
//        }
//        else {
//            cout << arr[i] << ' ';
//            i++; j++;
//        }
//    }
//    while (i < a)
//    {
//        cout << arr[i] << ' ';
//        i++;
//    }
//    while (j < b)
//    {
//        cout << brr[j] << ' ';
//        j++;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
////最长回文子序列
//#include <cstdio>
//#include <iostream>
//#include <string>
//using namespace std;
//
//int Ishave(string s, char t, int i)
//{
//    int ret = -1;
//    for (int j = i + 1; j < s.size(); j++)
//    {
//        if (t == s[j])
//        {
//            ret = j;
//        }
//    }
//    return ret;
//}
//int main() {
//    char ch;
//    ch = getchar();
//    string s;
//    while (ch != '\n')
//    {
//        s += ch;
//        ch = getchar();
//    }
//    int len = s.size();
//    char arr[len];
//    for (int i = 0; i < s.size(); i++)
//    {
//        arr[i] = '0';
//    }
//    for (int i = 0; i < s.size(); i++)
//    {
//        int j = Ishave(s, s[i], i);
//        if (j != -1)
//        {
//            arr[i] = arr[j] = s[i];
//        }
//    }
//    int i = 0, j = len - 1;
//    for (i; i < len; i++)
//    {
//        if (arr[i] != '0')
//            break;
//    }
//    for (j; j >= 0; j--)
//    {
//        if (arr[i] == arr[j])
//            break;
//    }
//    int sum = 0;
//    while (i <= j)
//    {
//        if (arr[i] == arr[j] && arr[i] != '0')
//        {
//            i++; j--;
//            sum += 2;
//        }
//        else if (arr[i] == '0')
//        {
//            i++;
//        }
//        else if (arr[j] == '0')
//        {
//            j--;
//        }
//        else {
//            i++; j--;
//        }
//        if (i == j)
//        {
//            sum += 1;
//            break;
//        }
//    }
//    cout << sum << endl;
//    // cout<<i<<j<<endl;
//    // for(int i=0;i<s.size();i++)
//    // {
//    //     cout<<arr[i]<<' ';
//    // }
//    //cout<<s;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
////day23
////打怪
//#include <iostream>
//using namespace std;
//
//int main() {
//    int t;
//    cin >> t;
//    while (t--)
//    {
//        int h, a, H, A;
//        cin >> h >> a >> H >> A;
//        //cout<<h<<a<<H<<A;
//        int flag = 0;
//        if (A <= 0 || a >= H)
//        {
//            cout << -1 << endl;
//            flag = 1;
//        }
//        if (flag == 1)
//        {
//            continue;
//        }
//        int sum = 0;
//        while (h > 0)
//        {
//            int tmp = H;
//            while (tmp > 0)
//            {
//                tmp -= a;
//                if (tmp > 0)
//                    h -= A;
//                if (h <= 0)
//                {
//                    cout << sum << endl;
//                    break;
//                }
//            }
//            sum++;
//        }
//
//    }
//
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////字符串分类
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//bool Issame(vector<vector<int>> v, int i, int j)
//{
//    for (int k = 0; k < 200; k++)
//    {
//        if (v[i][k] != v[j][k])
//            return false;
//    }
//    return true;
//}
//int main() {
//    int n;
//    cin >> n;
//    vector<string> vs;
//    vs.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        char arr[55];
//        scanf("%s", arr);
//        vs[i] += arr;
//    }
//    int sum = 1;
//    vector<vector<int>> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        v[i].resize(200);
//        for (int j = 0; j < 200; j++)
//            v[i][j] = 0;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < vs[i].size(); j++)
//        {
//            v[i][vs[i][j]]++;
//        }
//    }
//    bool arr[n + 1];
//    for (int i = 0; i <= n; i++)
//        arr[i] = false;
//    for (int i = 0; i < n; i++)
//    {
//        arr[i] = true;
//        for (int j = i + 1; j < n; j++)
//        {
//            if (arr[j] != true)
//            {
//                if (Issame(v, i, j))
//                {
//                    arr[j] = true;;
//                }
//                else {
//                    sum++;
//                }
//            }
//        }
//    }
//    cout << sum << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<vs[i]<<endl;
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////城市群数量
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param m int整型vector<vector<>>
//         * @return int整型
//         */
//    bool Ishave(vector<vector<int> >& tmp, int i, int j)
//    {
//        if (i - 1 >= 0 && tmp[i - 1][j] == 1)
//        {
//            return true;
//        }
//        else if (j - 1 >= 0 && tmp[i][j - 1] == 1)
//        {
//            return true;
//        }
//        else if (j + 1 < tmp[i].size() && tmp[i][j + 1] == 1)
//        {
//            return true;
//        }
//        else if (i + 1 < tmp.size() && tmp[i + 1][j] == 1)
//        {
//            return true;
//        }
//        return false;
//    }
//    int citys(vector<vector<int> >& m) {
//        // write code here
//        vector<vector<int>> tmp = m;
//        for (int i = 0; i < m.size(); i++)
//        {
//            for (int j = 0; j < m[i].size(); j++)
//            {
//                if (tmp[i][j] == 1 && Ishave(tmp, i, j))
//                {
//                    tmp[i][j] = 0;
//                }
//            }
//        }
//        int ret = 0;
//        for (int i = 0; i < m.size(); i++)
//        {
//            for (int j = 0; j < m[i].size(); j++)
//            {
//                if (tmp[i][j] == 1)
//                {
//                    ret++;
//                }
//            }
//        }
//        // for(int i=0;i<m.size();i++)
//        // {
//        //     for(int j=0;j<m[i].size();j++)
//        //     {
//        //         if(m[i][j]==1&&Ishave(m,i,j))
//        //         {
//        //             m[i][j]=0;
//        //             // for(int x=0;x<m.size();x++)
//        //             // {
//        //             //     for(int y=0;y<m[i].size();y++)
//        //             //     {
//        //             //         cout<<m[x][y]<<' ';
//        //             //     }
//        //             //     cout<<endl;
//        //             // }
//        //         }
//        //     }
//        // }
//        // int ret=0;
//        // for(int i=0;i<m.size();i++)
//        // {
//        //     for(int j=0;j<m[i].size();j++)
//        //     {
//        //         if(m[i][j]==1)
//        //         {
//        //             ret++;
//        //         }
//        //     }
//        // }
//        return ret;
//    }
//};
//
//
//
//
//
//
//
//
//
////Day24
////平衡二叉树
///**
// * struct TreeNode {
// *  int val;
// *  struct TreeNode *left;
// *  struct TreeNode *right;
// *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// * };
// */
//#include <cstddef>
//    class Solution {
//    public:
//            /**
//             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//             *
//             *
//             * @param pRoot TreeNode类
//             * @return bool布尔型
//             */
//        bool IsBalanced_Solution(TreeNode* pRoot) {
//            // write code here
//            if (pRoot == nullptr || (pRoot->left == nullptr && pRoot->right == nullptr))
//                return true;
//            int _left = 11100;
//            int _right = 11100;
//            if (pRoot->left != nullptr)
//            {
//                _left = (pRoot->left)->val;
//            }
//            if (pRoot->right != nullptr)
//            {
//                _right = (pRoot->right)->val;
//            }
//            // int _left=(pRoot->left)->val;
//            // int _right=_right=(pRoot->right)->val;
//            if ((int)abs(_left - _right) > 1)
//                return false;
//            return IsBalanced_Solution(pRoot->left) && IsBalanced_Solution(pRoot->right);
//
//        }
//};
//
//
//
//
////最大子矩阵
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<vector<int>> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        v[i].resize(n);
//        for (int j = 0; j < n; j++)
//        {
//            cin >> v[i][j];
//        }
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            cout << v[i][j] << ' ';
//        }
//        cout << endl;
//    }
//
//}
//// 64 位输出请用 printf("%lld")
//
//
//
////小葱的01串
//#include <iostream>
//#include <string>
//using namespace std;
//
//bool Number(string t, int s1, int s0)
//{
//    for (int i = 0; i < t.size(); i++)
//    {
//        if (t[i] == '1')
//            s1--;
//        else
//            s0--;
//    }
//    //cout<<t.size()<<endl;
//    //cout<<s1<<s0<<endl;
//    if (s1 == s0 && s1 == 0)
//        return true;
//    return false;
//}
//int main() {
//    int n;
//    cin >> n;
//    char arr[n];
//    scanf("%s", arr);
//    string s = arr;
//    //cout<<s<<endl;
//    int sum1 = 0;
//    int sum0 = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (arr[i] == '1')
//            sum1++;
//        else
//            sum0++;
//    }
//    //cout<<sum1<<sum0<<endl;
//    int s1 = sum1 / 2;
//    int s0 = sum0 / 2;
//    int qu = s1 + s0;
//    int i = 0;
//    int ret = 0;
//    while (i < s.size())
//    {
//        int j = i;
//        int k = 0;
//        string tmp;
//        while (k < qu)
//        {
//            tmp += s[j];
//            j++;
//            if (j > s.size() - 1)
//                j = 0;
//            k++;
//        }
//        if (Number(tmp, s1, s0))
//        {
//            ret++;
//        }
//        //cout<<tmp<<endl;
//        i++;
//    }
//    cout << ret << endl;
//    //cout<<sum1<<' '<<sum0;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
////数组中两个字符串的最小距离（优化：贪心）O(N)
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    string str1, str2;
//    cin >> str1 >> str2;
//    string str[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> str[i];
//    }
//    int prev1 = -1, prev2 = -1;
//    int ret = 1000000;
//    for (int i = 0; i < n; i++)
//    {
//        if (str[i].compare(str1) == 0)
//        {
//            prev1 = i;
//            if (prev2 != -1)
//            {
//                ret = ret < abs(prev2 - prev1) ? ret : abs(prev2 - prev1);
//            }
//        }
//        if (str[i].compare(str2) == 0)
//        {
//            prev2 = i;
//            if (prev1 != -1)
//            {
//                ret = ret < abs(prev2 - prev1) ? ret : abs(prev2 - prev1);
//            }
//        }
//    }
//    if (prev1 == -1 || prev2 == -1)
//    {
//        cout << -1 << endl;
//        return 0;
//    }
//    cout << ret << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<str[i]<<endl;
//    // }
//    // cout<<str1<<' '<<str2<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
////Day25
////笨小猴
//#include <cmath>
//#include <iostream>
//#include <algorithm>
//using namespace std;
//
//bool Iszhi(int a)
//{
//    if (a == 0 || a == 1)
//        return false;
//    if (a == 2)
//        return true;
//    for (int i = 2; i <= a / 2; i++)
//    {
//        if (a % i == 0)
//            return false;
//    }
//    return true;
//}
//int main() {
//    string s;
//    cin >> s;
//    //cout<<s;
//    int arr[150] = { 0 };
//    for (int i = 0; i < s.size(); i++)
//    {
//        arr[s[i]]++;
//    }
//    int max = -1, min = 1000;
//    for (int i = 0; i < 150; i++)
//    {
//        if (arr[i] > max)
//        {
//            max = arr[i];
//        }
//        if (arr[i] < min && arr[i] != 0)
//        {
//            min = arr[i];
//        }
//    }
//    int ret = max - min;
//    if (Iszhi(ret))
//    {
//        cout << "Lucky Word" << endl;
//        cout << ret;
//    }
//    else {
//        cout << "No Answer" << endl;
//        cout << 0;
//    }
//}
//// 64 位输出请用 printf("%lld")
//// 
//// 
////主持人调度
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param schedule int整型vector<vector<>>
//         * @return bool布尔型
//         */
//    bool hostschedule(vector<vector<int> >& schedule) {
//        // write code here
//        for (int i = 0; i + 1 < schedule.size(); i++)
//        {
//            //cout<<1<<endl;
//            if (schedule[i][1] > schedule[i + 1][0])
//                return false;
//        }
//        return true;
//    }
//};
//
//
////分割等和子集
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    long long arr[n];
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        long long sum = 0;
//        for (int j = 0; j < n; j++)
//        {
//            if (j != i)
//            {
//                sum += arr[j];
//            }
//        }
//        if (sum == arr[i])
//        {
//            cout << "true" << endl;
//            return 0;
//        }
//    }
//    cout << "false" << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
//
////Day26
////小红的ABC
//#include <iostream>
//using namespace std;
//
//int Ishui(string s, int i, int j)
//{
//    int i1 = i, j1 = j;
//    while (i1 <= j1)
//    {
//        if (s[i1] != s[j1])
//            return 0;
//        i1++; j1--;
//    }
//    return j - i + 1;
//}
//int main() {
//    string s;
//    cin >> s;
//    long long sum = -1;
//    for (int i = 0; i < s.size(); i++)
//    {
//        for (int j = i + 1; j < s.size(); j++)
//        {
//            if (s[i] == s[j])
//            {
//                int tmp = Ishui(s, i, j);
//                if (tmp)
//                {
//                    sum = sum > tmp ? sum : tmp;
//                }
//            }
//        }
//    }
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////不相邻取数
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    int sum1 = 0, sum2 = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (i % 2 == 0)
//        {
//            sum1 += v[i];
//        }
//        else {
//            sum2 += v[i];
//        }
//    }
//    int max = sum1 > sum2 ? sum1 : sum2;
//    cout << max << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<v[i];
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
////空调遥控
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, q;
//    cin >> n >> q;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    sort(v.begin(), v.end());
//    int sum = 0;
//    for (int i = 1; i < n - 1; i++)
//    {
//        int tmp = 0;
//        int min = v[i] - q;
//        int max = v[i] + q;
//        for (int j = 0; j < n; j++)
//        {
//            if (v[j] > max)
//                break;
//            if (v[j] >= min)
//            {
//                tmp++;
//            }
//        }
//        sum = sum > tmp ? sum : tmp;
//    }
//    cout << sum << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<v[i];
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
//
////Day27
////Kotori和气球
//#include <iostream>
//using namespace std;
//
//long long jie(int n)
//{
//    long long ret = 1;
//    for (int i = 1; i <= n; i++)
//    {
//        ret *= i;
//    }
//    return ret;
//}
//int main() {
//    int n, m;
//    cin >> n >> m;
//    long long sum = n * (jie(n - 1) / jie(((n - 1) - (m - 1)))) % 109;
//    if (n == m)
//        sum = 1;
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////走迷宫
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int xs, ys;
//    cin >> xs >> ys;
//    int xt, yt;
//    cin >> xt >> yt;
//    vector<string> vs;
//    vs.resize(n);
//    //cout<<xt<<yt<<endl;
//    for (int i = 0; i < n; i++)
//    {
//        vs[i].resize(m);
//        for (int j = 0; j < m; j++)
//            cin >> vs[i][j];
//    }
//    if (vs[xt - 1][yt - 1] == '*')
//        cout << "-1" << endl;
//    // for(int i=0;i<n;i++)
//    // {
//    //     for(int j=0;j<m;j++)
//    //         cout<<vs[i][j];
//    //         cout<<endl;
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
////主持人调度（二）
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * 计算成功举办活动需要多少名主持人
//         * @param n int整型 有n个活动
//         * @param startEnd int整型vector<vector<>> startEnd[i][0]用于表示第i个活动的开始时间，startEnd[i][1]表示第i个活动的结束时间
//         * @return int整型
//         */
//    int minmumNumberOfHost(int n, vector<vector<int> >& startEnd) {
//        // write code here
//        int sum = 1;
//        for (int i = 0; i + 1 < n; i++)
//        {
//            if (startEnd[i][1] > startEnd[i + 1][0])
//                sum++;
//        }
//        // for(int i=0;i+1<n;i++)
//        // {
//        //     if(startEnd[i][0]==startEnd[i+1][0])
//        //         sum++;
//        // }
//        // for(int i=0;i<n;i++)
//        // {
//        //     for(int j=0;j<n;j++)
//        //     {
//        //         if(startEnd[i][0]<startEnd[j][1]&&startEnd[i][0]>startEnd[j][0])
//        //             sum++;
//        //     }
//        // }
//        return sum;
//    }
//};
//
//
//
//
//
//
////Day28
////游游的重组数组
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<string> vs;
//    vs.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> vs[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        int flag = 0;
//        int twe_i = 0;
//        int j = 0;
//        int t_f = 0;
//        for (j = 0; j < vs[i].size(); j++)
//        {
//            if ((vs[i][vs[i].size() - 1] - '0') % 2 == 0)
//            {
//                t_f = 1; break;
//            }
//            if ((vs[i][j] - '0') % 2 == 0)
//            {
//                flag = 1;
//                twe_i = j;
//            }
//        }
//        if (t_f == 1)
//            continue;
//        if (flag == 0)
//        {
//            vs[i] = "-1";
//            continue;
//        }
//        char tmp1 = vs[i][j - 1];
//        char tmp2 = vs[i][twe_i];
//        vs[i][j - 1] = tmp2;
//        vs[i][twe_i] = tmp1;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        cout << vs[i] << endl;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
////体操队形
//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//long long Ishave(int time)
//{
//    int ret = 1;
//    for (int i = 1; i <= time; i++)
//    {
//        ret *= i;
//    }
//    return ret;
//}
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    //sort(v.begin(),v.end());
//    for (int i = 0; i < n; i++)
//    {
//        if (v[i] - 1 == i)
//        {
//            v[i] = -1;
//        }
//    }
//    int time = 0;
//    for (int i = 0; i < n; i++)
//    {
//        if (v[i] == -1)
//        {
//            time++;
//        }
//    }
//    long long ret = Ishave(time);
//    cout << ret << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////Day29
////排序子序列（题目不明白）
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int t;
//    cin >> t;
//    vector<int> v;
//    v.resize(t);
//    for (int i = 0; i < t; i++)
//    {
//        cin >> v[i];
//    }
//    // int i=0,j=1;
//    // while()
//    // {
//    //     if(v[i]==v[j])
//    //     {
//    //     }
//    // }
//    int flag = 0;
//    for (int i = 0; i + 1 < t; i++)
//    {
//        if (v[i] == v[i + 1])
//        {
//            flag = 1;
//            break;
//        }
//    }
//    if (flag == 1)
//        cout << 2 << endl;
//    else
//        cout << 1 << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////消减整数
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int t;
//    cin >> t;
//    int h;
//    while (t)
//    {
//        int sum = 0;
//        int j = 1;
//        cin >> h;
//        if (h % 2 == 0)
//        {
//            h -= 2;
//            sum += 2;
//            j *= 2;
//            while (h)
//            {
//                h -= j;
//                if (h % (j * 2) == 0)
//                    j *= 2;
//                sum++;
//            }
//        }
//        else {
//            h--;
//            sum++;
//            j *= 2;
//            while (h)
//            {
//                h -= j;
//                if (h % (j * 2) == 0)
//                    j *= 2;
//                sum++;
//            }
//        }
//        cout << sum << endl;
//        t--;
//    }
//    // vector<int> v;
//    // v.resize(t);
//    // for(int i=0;i<t;i++)
//    // {
//    //     cin>>v[i];
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
////最长上升子序列（二），不会
//#include <vector>
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * 该数组最长严格上升子序列的长度
//         * @param a int整型vector 给定的数组
//         * @return int整型
//         */
//    int LIS(vector<int>& a) {
//        // write code here
//        vector<int> di;
//        di.resize(a.size());
//        int flag1 = 0;
//        for (int i = 0; i + 1 < a.size(); i++)
//        {
//            if (a[i + 1] < a[i])
//            {
//                flag1 = 1;
//                break;
//            }
//        }
//        if (flag1 == 0)
//            return a.size();
//        else
//            return a.size() - 1;
//        return 0;
//    }
//};
//
//
//
//
//
//
////Day30
////爱吃素
//#include <cmath>
//#include <iostream>
//using namespace std;
//
//bool Issu(long long sum)
//{
//    if (sum == 1)
//        return false;
//    if (sum == 2 || sum == 3)
//        return true;
//    for (int i = 2; i <= sqrt(sum); i++)
//    {
//        if (sum % i == 0)
//            return false;
//    }
//    return true;
//}
//int main() {
//    int n;
//    cin >> n;
//    while (n)
//    {
//        long long a, b;
//        cin >> a >> b;
//        long long sum = a * b;
//        if (Issu(sum))
//        {
//            cout << "YES" << endl;
//        }
//        else {
//            cout << "NO" << endl;
//        }
//        n--;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
////相差不超过k的个数
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, k;
//    cin >> n >> k;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<v[i]<<' ';
//    // }
//    sort(v.begin(), v.end());
//    // int mid=v.size()/2;
//    int i = 0, j = v.size() - 1;
//    while (i < v.size())
//    {
//        if (v[j] - v[i] <= k)
//        {
//            break;
//        }
//        i++;
//    }
//    // // cout<<i<<j;
//    int sum = j - i + 1;
//    // int sum=100000;
//    // int i=0,j=v.size()-1;
//    // while(j>=0)
//    // {
//    //     if(v[j]-v[i]<=k)
//    //     {
//    //         break;
//    //     }
//    //     j--;;
//    // }
//    // // cout<<i<<j;
//    // sum=sum>j-i+1?j-i+1:sum;
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////最长公共子序列
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    string s1, s2;
//    cin >> s1 >> s2;
//    vector<int> v1;
//    vector<int> v2;
//    v1.resize(150);
//    v2.resize(150);
//    for (int i = 0; i < 150; i++)
//    {
//        v1[i] = v2[i] = 0;
//    }
//    for (int i = 0; i < s1.size(); i++)
//    {
//        v1[s1[i]]++;
//    }
//    for (int i = 0; i < s2.size(); i++)
//    {
//        v2[s2[i]]++;
//    }
//    int flag = 0;
//    for (int i = 0; i < 150; i++)
//    {
//        if (v1[i] == v2[i] && v1[i] != 0)
//        {
//            flag = 1;
//            break;
//        }
//    }
//    if (flag == 0)
//    {
//        cout << 0 << endl;
//        return 0;
//    }
//
//    //cout<<s1<<s2;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
////Day30
////小红的口罩
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, k;
//    cin >> n >> k;
//    vector<int> arr;
//    arr.resize(n);
//    for (int i = 0; i < n; i++)
//        cin >> arr[i];
//    sort(arr.begin(), arr.end());
//    int day = 0;
//    int sum = 0;
//    int i = 0;
//    while (sum < k)
//    {
//        //cout<<arr[i]<<endl;
//        sum += arr[i];
//        if (sum < k)
//            day++;
//        int flag = 0;
//        if (i + 1 < arr.size())
//        {
//            if (arr[i] > arr[i + 1])
//            {
//                //cout<<arr[i+1]<<endl;
//                i++;
//                flag = 1;
//            }
//        }
//        if (flag == 0)
//            arr[i] *= 2;
//    }
//    cout << day << endl;
//    // for(int i=0;i<n;i++)
//    //     cout<<arr[i];
//}
//// 64 位输出请用 printf("%lld")
//
//
////春游
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int t;
//    cin >> t;
//    while (t)
//    {
//        int n, a, b;
//        cin >> n >> a >> b;
//        int sum = 0;
//        if (n % 2 == 1)
//        {
//            if (2 * a > b)
//            {
//                while (n >= 3)
//                {
//                    sum += b;
//                    n -= 3;
//                }
//                if (n >= 1)
//                {
//                    sum += a;
//                }
//            }
//            else {
//                while (n >= 2)
//                {
//                    sum += a;
//                    n -= 2;
//                }
//                if (n >= 1)
//                {
//                    sum += a;
//                }
//            }
//        }
//        else
//        {
//            if (2 * a > b)
//            {
//                while (n >= 3)
//                {
//                    sum += b;
//                    n -= 3;
//                }
//                if (n >= 1)
//                {
//                    sum += a;
//                }
//            }
//            else {
//                while (n >= 2)
//                {
//                    sum += a;
//                    n -= 2;
//                }
//                if (n >= 1)
//                {
//                    sum += a;
//                }
//            }
//        }
//        cout << sum << endl;
//        t--;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
////数位染色
//#include <cstdio>
//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    string arr;
//    char ch;
//    //int n=0;
//    ch = getchar();
//    while (ch != '\n')
//    {
//        arr.push_back(ch);
//        ch = getchar();
//    }
//    int sum = 0;
//    for (int i = 0; i < arr.size(); i++)
//    {
//        sum += arr[i] - '0';
//    }
//    if (sum % 2 == 1)
//        cout << "No" << endl;
//    else
//    {
//        sum /= 2;
//        cout << "Yes" << endl;
//    };
//    //cout<<arr<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
////Day32
////素数回文
//#include <cmath>
//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//
//bool Isprime(long long a)
//{
//    if (a == 1)
//        return false;
//    if (a == 2)
//        return true;
//    for (int i = 2; i <= sqrt(a); i++)
//    {
//        if (a % i == 0)
//            return false;
//    }
//    return true;
//}
//int main() {
//    long long n;
//    cin >> n;
//    long long tmp = n;
//    string s;
//    while (tmp)
//    {
//        s += tmp % 10 + '0';
//        tmp /= 10;
//    }
//    // //默认递增
//    // bool flag=true;
//    // if(s[0]>s[1])
//    //     flag=false;
//    // if(flag)
//    // {
//    //     for(int i=0;i+1<s.size();i++)
//    //     {
//    //         if(s[i]>s[i+1])
//    //         {
//    //             cout<<"noprime"<<endl;
//    //             return 0;
//    //         }
//    //     }
//    // }
//    // else {
//
//    // }
//    //int arr[10]={0};
//    reverse(s.begin(), s.end());
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] == '0')
//        {
//            cout << "noprime" << endl;
//            return 0;
//        }
//        //arr[s[i]-'0']++;
//    }
//    // for(int i=1;i<=9;i++)
//    // {
//    //     if(arr[i]>1)
//    //     {
//    //         cout<<"noprime"<<endl;
//    //         return 0;
//    //     }
//    // }
//    int j = s.size() - 2;
//    while (j >= 0)
//    {
//        s += s[j];
//        j--;
//    }
//    long long ret = 0;
//    j = s.size() - 1;
//    long long num = 0;
//    while (j >= 0)
//    {
//        ret += (s[j] - '0') * (int)pow(10, num);
//        num++; j--;
//    }
//    if (Isprime(ret))
//    {
//        cout << "prime" << endl;
//    }
//    else {
//        cout << "noprime" << endl;
//    }
//    //cout<<ret;
//    //cout<<s;
//}
//// 64 位输出请用 printf("%lld")
//
//
////活动安排
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v1;
//    vector<int> v2;
//    v1.resize(n);
//    v2.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v1[i] >> v2[i];
//    }
//    int max = 0;
//    int k = 0;
//    while (k < v1.size())
//    {
//        int i = k;
//        //int flag=1;
//        int sum = 1;
//        int j = 0;
//        while (j < n)
//        {
//            if (v2[i] == v1[j])
//            {
//                i = j;
//                sum++;
//            }
//            j++;
//        }
//        if (sum > max)
//            max = sum;
//        k++;
//    }
//    cout << max << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////合唱团
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, k, d;
//    cin >> n >> k >> d;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//        cin >> v[i];
//    int i = 0;
//    int arr[n];
//    long long sum = 0;
//    if (d >= n)
//    {
//        sort(v.begin(), v.end());
//        sum = v[v.size() - 1];
//        k--;
//        int j = v.size() - 2;
//        while (k)
//        {
//            sum *= v[j];
//            j--;
//            k--;
//        }
//    }
//    else {
//        while (i + d < n)
//        {
//            vector<int> tmp(v.begin() + i, v.begin() + i + d + 1);
//            sort(tmp.begin(), tmp.end());
//            long long t_sum = tmp[tmp.size() - 1];
//            int k1 = k - 1;
//            int j = tmp.size() - 2;
//            while (k1)
//            {
//                t_sum *= tmp[j];
//                j--;
//                k1--;
//            }
//            if (t_sum > sum)
//                sum = t_sum;
//            // for(int x=0;x<tmp.size();x++)
//            //     cout<<tmp[x]<<' ';
//            // cout<<endl;
//            i++;
//        }
//    }
//    cout << sum;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////Day33
////跳台阶扩展问题
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int sum = pow(2, n - 1);
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////包含不超过两种字符的最长子串
//#include <iostream>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//    int arr[s.size()];
//    for (int i = 0; i < s.size(); i++)
//        arr[i] = 0;
//    int k = 0;
//    int len = 1;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] == s[i + 1])
//        {
//            len = 1;
//            int j;
//            for (j = i + 1; j < s.size(); j++)
//            {
//                if (s[i] == s[j])
//                    len++;
//                else
//                    break;
//            }
//            i = j - 1;
//            //cout<<len<<endl;
//        }
//        arr[k++] = len;
//        len = 1;
//    }
//    int max = 0;
//    for (int i = 0; i + 1 < k; i++)
//    {
//        if (max < arr[i] + arr[i + 1])
//            max = arr[i] + arr[i + 1];
//    }
//    cout << max;
//    // for(int i=0;i<k;i++)
//    //     cout<<arr[i]<<' ';
//    //cout<<s;
//    // int max=0;
//    // int max_i=0;
//    // for(int i=0;i+1<s.size();i++)
//    // {
//    //     if(s[i]==s[i+1])
//    //     {
//    //         int len=1;
//    //         for(int j=i+1;j<s.size();j++)
//    //         {
//    //             if(s[i]==s[j])
//    //                 len++;
//    //             else
//    //                 break;
//    //         }
//    //         if(len>max)
//    //         {
//    //             max=len;
//    //             max_i=i;
//    //         }
//    //     }
//    // }
//    // //cout<<max<<' '<<max_i<<endl;
//    // if(max==0)
//    //     cout<<2<<endl;
//    // else
//    // {
//    //     int x=max_i-1;
//    //     int y=max_i+max;
//    //     int len1=1;
//    //     int len2=1;
//    //     while(x>=0)
//    //     {
//    //         if(x-1>=0&&s[x]==s[x-1])
//    //         {
//    //             len1++;
//    //         }
//    //         else {
//    //         break;
//    //         }
//    //         x--;
//    //     }
//    //     while(y<s.size())
//    //     {
//    //         if(y+1<s.size()&&s[y]==s[y+1])
//    //         {
//    //             len2++;
//    //         }
//    //         else {
//    //         break;
//    //         }
//    //         y++;
//    //     }
//    //     len1=len1>len2?len1:len2;
//    //     max+=len1;
//    //     cout<<max<<endl;
//    // }
//    // //cout<<max<<' '<<max_i<<endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////字符串的排列
//#include <vector>
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param str string字符串
//         * @return string字符串vector
//         */
//    int jie(int n)
//    {
//        int ret = 1;
//        for (int i = 1; i <= n; i++)
//            ret *= i;
//        return ret;
//    }
//    vector<string> Permutation(string str) {
//        // write code here
//        vector<string> vs;
//        int n = str.size();
//        int sum = jie(str.size());
//        vs.resize(sum);
//        int j = 0;
//        for (int i = 0; i < n; i++)
//        {
//            int n1 = n - 1;
//            while (n1)
//            {
//                vs[j++] += str[i];
//                n1--;
//            }
//        }
//
//        //cout<<sum;
//        // for(int i=0;i<str.size();i++)
//        // {
//        //     for(int j=0;j<str.size();j++)
//        //     {
//        //     }
//        // }
//        return vs;
//    }
//};
//
//
//
//
//
//
//
//
////Day34
////ISBN号码
//#include <iostream>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//    int arr[10];
//    int n = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (s[i] >= '0' && s[i] <= '9')
//        {
//            arr[n++] = s[i] - '0';
//        }
//    }
//    long long sum = 0;
//    for (int i = 0; i < n - 1; i++)
//    {
//        sum += arr[i] * (i + 1);
//        sum %= 11;
//    }
//    sum %= 11;
//    char ch;
//    if (sum == 10)
//    {
//        ch = 'X';
//    }
//    else {
//        ch = sum + '0';
//    }
//    if (ch == s[s.size() - 1])
//    {
//        cout << "Right";
//    }
//    else {
//        s[s.size() - 1] = ch;
//        cout << s;
//    }
//    // for(int i=0;i<n;i++)
//    //     cout<<arr[i];
//}
//// 64 位输出请用 printf("%lld")
//
//
////Kotori和迷宫
//#include <iostream>
//#include <vector>
//#include <string>
//using namespace std;
//
//struct people
//{
//    int i, j;
//    int d, n, x, b;
//};
//int main() {
//    int n, m;
//    cin >> n >> m;
//    vector<string> vs;
//    vs.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> vs[i];
//    }
//    // for(int i=0;i<n;i++)
//    // {
//    //     cout<<vs[i]<<endl;
//    // }
//    int first_i, first_j;
//    for (int i = 0; i < n; i++)
//    {
//        bool flag = false;
//        for (int j = 0; j < m; j++)
//        {
//            if (vs[i][j] == 'k')
//            {
//                first_i = i;
//                first_j = j;
//                flag = true;
//                break;
//            }
//        }
//        if (flag)
//            break;
//    }
//    vector<int> tmp;
//    cout << -1;
//}
//// 64 位输出请用 printf("%lld")
//
//
////矩阵最长递增路径
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * 递增路径的最大长度
//         * @param matrix int整型vector<vector<>> 描述矩阵的每个数
//         * @return int整型
//         */
//    void len(vector<vector<int> >& matrix, int x, int y, int& ret)
//    {
//        if (x - 1 >= 0)
//        {
//            if (matrix[x - 1][y] > matrix[x][y])
//            {
//                ret++;
//                len(matrix, x - 1, y, ret);
//            }
//        }
//        else if (y - 1 >= 0)
//        {
//            if (matrix[x][y - 1] > matrix[x][y])
//            {
//                ret++;
//                len(matrix, x, y - 1, ret);
//            }
//        }
//        else if (y + 1 < matrix[x].size())
//        {
//            if (matrix[x][y + 1] > matrix[x][y])
//            {
//                ret++;
//                len(matrix, x, y + 1, ret);
//            }
//        }
//        else if (x + 1 < matrix.size())
//        {
//            if (matrix[x + 1][y] > matrix[x][y])
//            {
//                ret++;
//                len(matrix, x + 1, y, ret);
//            }
//        }
//    }
//    int solve(vector<vector<int> >& matrix) {
//        // write code here
//        // vector<vector<int> > di;
//        // di.resize(matrix.size());
//        // for(int i=0;i<di.size();i++)
//        //     di[i].resize(matrix[i].size());
//        // di[0][0]=1;
//        int min_i = 0, min_j = 0;
//        int min = matrix[0][0];
//        for (int i = 0; i < matrix.size(); i++)
//        {
//            for (int j = 0; j < matrix[i].size(); j++)
//            {
//                if (min > matrix[i][j])
//                {
//                    min = matrix[i][j];
//                    min_i = i;
//                    min_j = j;
//                }
//            }
//        }
//        int ret = 0;
//        len(matrix, min_i, min_j, ret);
//        return ret;
//        //cout<<min_i<<min_j;
//        return 0;
//    }
//};
//
//
//
//
//
//
//
//
////Day35
////奇位数丢弃
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int arr[n + 1];
//    for (int i = 0; i <= n; i++)
//    {
//        arr[i] = i;
//    }
//    vector<int> v;
//    for (int i = 0; i < n; i++)
//    {
//        if ((i + 1) % 2 == 0)
//        {
//            v.push_back(arr[i]);
//        }
//    }
//    // for(int i=0;i<v.size();i++)
//    // {
//    //     cout<<v[i];
//    // }
//    //cout<<v.size()<<endl;
//    while (v.size() != 1)
//    {
//        vector<int> tmp;
//        for (int i = 0; i < v.size(); i++)
//        {
//            if ((i + 1) % 2 == 0)
//            {
//                tmp.push_back(v[i]);
//            }
//        }
//        v = tmp;
//        //cout<<v.size()<<endl;
//    }
//    cout << v[0] << endl;
//    // int sum=n+1;
//    // while(n!=1)
//    // {
//    // }
//    // for(int i=0;i<=n;i++)
//    // {
//    //     if(arr[i]!=-1)
//    //         cout<<arr[i]<<endl;
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
////求和
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int arr[n];
//    for (int i = 0; i < n; i++)
//    {
//        arr[i] = i + 1;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        if (m - arr[i] < arr[i + 1])
//            break;
//        else
//        {
//            cout << arr[i] << ' ' << m - arr[i] << endl;
//        }
//    }
//    if (n == m)
//        cout << m << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
////计算字符串的编辑距离
//#include <iostream>
//using namespace std;
//
//int main() {
//    string s1, s2;
//    cin >> s1 >> s2;
//    //cout<<s1<<s2;
//    string::iterator it1 = s1.begin();
//    string::iterator it2 = s2.begin();
//    int sum = 0;
//    while (it1 != s1.end() && it2 != s2.end())
//    {
//        if (*it1 == *it2)
//        {
//            it1++; it2++;
//        }
//        else {
//            if (s1.size() < s2.size())
//            {
//                //it1=s1.insert(it1, *it2);
//                *it1 = *it2;
//                sum++;
//            }
//            else {
//                //it2=s2.insert(it2, *it1);
//                *it2 = *it1;
//                sum++;
//            }
//        }
//    }
//    while (it1 != s1.end())
//    {
//        it1 = s1.erase(it1);
//        sum++;
//    }
//    while (it2 != s2.end())
//    {
//        it2 = s2.erase(it2);
//        sum++;
//    }
//    cout << sum << endl;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////Day36
////提取不重复的整数
//#include <iostream>
//using namespace std;
//
//bool Ishave(string s, char ch)
//{
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (ch == s[i])
//            return false;
//    }
//    return true;
//}
//int main() {
//    int a;
//    cin >> a;
//    string s;
//    while (a)
//    {
//        char ch = a % 10 + '0';
//        if (Ishave(s, ch))
//            s += ch;
//        a /= 10;
//    }
//    cout << s;
//}
//// 64 位输出请用 printf("%lld")
//
//
////霍夫曼编码
////不会
//
//
////Abb
//#include <iostream>
//using namespace std;
//
//bool Ishave(string s, char ch)
//{
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (ch == s[i])
//            return false;
//    }
//    return true;
//}
//int main() {
//    int n;
//    cin >> n;
//    string s;
//    cin >> s;
//    //cout<<s;
//    string ret;
//    int sum = 0;
//    for (int i = 0; i < s.size(); i++)
//    {
//        if (Ishave(ret, s[i]))
//        {
//            ret += s[i];
//            string tmp;
//            tmp += s[i];
//            int flag = 0;
//            for (int j = i + 1; j < s.size(); j++)
//            {
//                if (Ishave(tmp, s[j]))
//                {
//                    flag = 1;
//                    tmp += s[j];
//                    break;
//                }
//            }
//            if (flag == 0)
//                break;
//            int t = 0;
//            for (int j = i + 1; j < s.size(); j++)
//            {
//                if (tmp[1] == s[j])
//                    t++;
//            }
//            t--;
//            while (t)
//            {
//                sum += t;
//                t--;
//            }
//            //cout<<sum<<endl;
//        }
//    }
//    cout << sum;
//
//    // int arr[150]={0};
//    // for(int i=0;i<s.size();i++)
//    // {
//    //     arr[s[i]]++;
//    // }
//    // for(int i=95;i<150;i++)
//    // {
//    //     if(arr[i]!=0)
//    //     {
//    //         int j=0;
//    //         while(i!=s[j])
//    //         {
//    //             j++;
//    //         }
//    //         for(int k=i+1;k<150;k++)
//    //         {
//    //             if(arr[k]!=0)
//    //             {
//    //             }
//    //         }
//    //     }
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
//#include <stack>
////最小栈
////思路：创建两个栈，一个存所有数据，一个存栈当前的最小数据
//class MinStack {
//public:
//    /** initialize your data structure here. */
//    MinStack() {
//
//    }
//
//    void push(int x) {
//        s.push(x);
//        if (s_min.size() == 0)
//            s_min.push(x);
//        else if (s.top() <= s_min.top())
//            s_min.push(x);
//    }
//
//    void pop() {
//        if (s.top() == s_min.top())
//            s_min.pop();
//        s.pop();
//    }
//
//    int top() {
//        return s.top();
//    }
//
//    int getMin() {
//        return s_min.top();
//    }
//    stack<int> s;
//    stack<int> s_min;
//};
//
///**
// * Your MinStack object will be instantiated and called as such:
// * MinStack* obj = new MinStack();
// * obj->push(x);
// * obj->pop();
// * int param_3 = obj->top();
// * int param_4 = obj->getMin();
// */
//
//
//
////栈的压入、弹出序列
//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     *
//     * @param pushV int整型vector
//     * @param popV int整型vector
//     * @return bool布尔型
//     */
//    bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {
//        // write code here
//        stack<int> s;
//        int j = 0;
//        for (int i = 0; i < popV.size(); i++)
//        {
//            if (!s.empty() && s.top() == popV[i])
//            {
//                s.pop();
//                continue;
//            }
//            while (pushV[j] != popV[i] && j < pushV.size())
//            {
//                s.push(pushV[j]);
//                j++;
//            }
//            if (j < pushV.size())
//                s.push(pushV[j++]);
//            if (s.top() == popV[i])
//            {
//                s.pop();
//                continue;
//            }
//            else {
//                return false;
//            }
//        }
//        return true;
//    }
//};
//
//
//
//
//
//
////Day37
////旋转字符串
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * 旋转字符串
//         * @param A string字符串
//         * @param B string字符串
//         * @return bool布尔型
//         */
//    bool solve(string A, string B) {
//        // write code here
//        if (A == B)
//            return true;
//
//        string::iterator it = A.begin();
//        while (it != A.end())
//        {
//            string tmp;
//            string::iterator it1 = it;
//            tmp.append(it1, A.end());
//            tmp.append(A.begin(), it1);
//            if (tmp == B)
//                return true;
//            it++;
//        }
//        return  false;
//    }
//};
//
//
////合并n个已排序的序列
///**
// * struct ListNode {
// *  int val;
// *  struct ListNode *next;
// *  ListNode(int x) : val(x), next(nullptr) {}
// * };
// */
//#include <vector>
//    class Solution {
//    public:
//            /**
//             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//             *
//             *
//             * @param lists ListNode类vector
//             * @return ListNode类
//             */
//
//        bool Isempty(vector<ListNode*>& lists)
//        {
//            for (int i = 0; i < lists.size(); i++)
//            {
//                if (lists[i] != nullptr)
//                    return true;
//            }
//            return false;
//        }
//        ListNode* mergeKLists(vector<ListNode*>& lists) {
//            // write code here
//            ListNode* ret = nullptr;
//
//            int min = 10000;
//            int min_i = -1;
//            for (int i = 0; i < lists.size(); i++)
//            {
//                if (lists[i] != nullptr && lists[i]->val < min)
//                {
//                    min = lists[i]->val;
//                    min_i = i;
//                }
//            }
//            ListNode* t;
//            t = new ListNode(min);
//            t->next = nullptr;
//            ret = t;
//            lists[min_i] = lists[min_i]->next;
//            ListNode* r = ret;
//            while (Isempty(lists))
//            {
//                min = 50000;
//                min_i = -1;
//                for (int i = 0; i < lists.size(); i++)
//                {
//                    if (lists[i] != nullptr && lists[i]->val < min)
//                    {
//                        min = lists[i]->val;
//                        min_i = i;
//                    }
//                }
//                ListNode* tmp;
//                tmp = new ListNode(min);
//                tmp->next = nullptr;
//                ret->next = tmp;
//                ret = ret->next;
//                lists[min_i] = lists[min_i]->next;
//            }
//            return r;
//        }
//};
//
//    
////滑雪
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    vector<vector<int>> vv;
//    vv.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        vv[i].resize(m);
//        for (int j = 0; j < m; j++)
//            cin >> vv[i][j];
//    }
//    int max = 0, max_i = 0, max_j = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            if (vv[i][j] > max)
//            {
//                max = vv[i][j];
//                max_i = i;
//                max_j = j;
//            }
//        }
//    }
//    cout << n * m;
//    //cout<<max_i<<max_j;
//    // for(int i=0;i<n;i++)
//    // {
//    //     for(int j=0;j<m;j++)
//    //         cout<<vv[i][j]<<' ';
//    //     cout<<endl;
//    // }
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
//
//
//
////Day38
////天使果冻
//#include <algorithm>
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//        cin >> v[i];
//    int first = v[0];
//    int second = v[1];
//    if (first < second)
//    {
//        int tmp = first;
//        first = second;
//        second = tmp;
//    }
//    vector<int> di;
//    di.resize(n);
//    di[0] = 0;
//    di[1] = second;
//    for (int i = 2; i < n; i++)
//    {
//        if (v[i] > first)
//        {
//            second = first;
//            first = v[i];
//        }
//        else if (v[i] <= first && v[i] > second)
//        {
//            second = v[i];
//        }
//        di[i] = second;
//    }
//    // for(int i=0;i<n;i++)
//    //     cout<<di[i]<<' ';
//    int q;
//    cin >> q;
//    while (q)
//    {
//        int num;
//        cin >> num;
//        cout << di[num - 1] << endl;
//        q--;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
////Dd爱旋转
//#include <any>
//#include <iostream>
//#include <type_traits>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<vector<int>> vv;
//    vv.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        vv[i].resize(n);
//        for (int j = 0; j < n; j++)
//            cin >> vv[i][j];
//    }
//    int q;
//    cin >> q;
//    while (q)
//    {
//        int x;
//        cin >> x;
//        vector<vector<int>> tmp;
//        tmp.resize(n);
//        for (int i = 0; i < n; i++)
//        {
//            tmp[i].resize(n);
//        }
//        if (x == 1)
//        {
//            for (int i = 0; i < n; i++)
//            {
//                for (int j = 0; j < n; j++)
//                {
//                    if (i == j)
//                    {
//                        //wap(vv[i][j],vv[n-1-i][n-1-i]);
//                        tmp[i][j] = vv[n - 1 - i][n - 1 - i];
//                    }
//                    else {
//                        //swap(vv[i][j],vv[j][i]);
//                        tmp[i][j] = vv[j][i];
//                    }
//                }
//            }
//        }
//        else {
//            for (int i = 0; i < n; i++)
//            {
//                for (int j = 0; j < n; j++)
//                {
//                    //swap(vv[i][j],vv[n-1-i][j]);
//                    tmp[i][j] = vv[n - 1 - i][j];
//                }
//            }
//        }
//        vv = tmp;
//        q--;
//    }
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//            cout << vv[i][j] << ' ';
//        cout << endl;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
//
////小红取数
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n, k;
//    cin >> n >> k;
//    vector<int> v;
//    v.resize(n);
//    int sum = 0;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//        sum += v[i];
//    }
//    while (sum >= 0)
//    {
//        if (sum % k == 0)
//            cout << sum;
//        else
//        {
//            int c = sum % k;
//            for (int i = 0; i < n; i++)
//            {
//                if (c == v[i])
//                {
//                    sum -= c;
//                    cout << sum;
//                    return 0;
//                }
//            }
//            cout << -1;
//            return 0;
//        }
//    }
//
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
//
//
////Day39
////神奇的字母（二）
//#include <cstdio>
//#include <iostream>
//using namespace std;
//
//int main() {
//    string s;
//    cin >> s;
//    getchar();
//    int arr[150] = { 0 };
//    while (!s.empty())
//    {
//        for (int i = 0; i < s.size(); i++)
//        {
//            arr[s[i]]++;
//        }
//        //cout<<s<<endl;
//        s.clear();
//        cin >> s;
//        getchar();
//    }
//    int max = 0;
//    char max_i = 0;
//    for (int i = 0; i < 150; i++)
//    {
//        if (arr[i] > max)
//        {
//            max = arr[i];
//            max_i = i;
//        }
//    }
//    cout << max_i << endl;
//}
//// 64 位输出请用 printf("%lld")
//
////字母编码
////不会哈夫曼编码
//
//
////最少的完全平方数
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    int arr[120];
//    for (int i = 0; i < 120; i++)
//    {
//        arr[i] = i * i;
//    }
//    int sum = 0;
//    while (n)
//    {
//        int a1;
//        for (int i = 0; i < 120; i++)
//        {
//            if (n < arr[i])
//            {
//                a1 = i - 1;
//                break;
//            }
//            else if (n == arr[i])
//            {
//                a1 = i;
//                break;
//            }
//        }
//        while (n >= arr[a1])
//        {
//            n -= arr[a1];
//            sum++;
//        }
//    }
//    cout << sum;
//}
//// 64 位输出请用 printf("%lld")
//
//
////逆波兰表达式求值
//class Solution {
//public:
//    int StrToInt(string str1)
//    {
//        int ret = 0;
//        int flag = 1;
//        if (str1[0] == '-')
//        {
//            flag = -1;
//            for (int i = 1; i < str1.size(); i++)
//            {
//                ret += (str1[i] - '0') * pow(10, str1.size() - 1 - i);
//            }
//            ret *= -1;
//        }
//        else {
//            for (int i = 0; i < str1.size(); i++)
//            {
//                ret += (str1[i] - '0') * pow(10, str1.size() - 1 - i);
//            }
//        }
//        return ret;
//    }
//    string IntToStr(int c)
//    {
//        string ret;
//        if (c < 0)
//        {
//            //ret.push_back('-');
//            c *= -1;
//            while (c)
//            {
//                int t = c % 10;
//                ret += t + '0';
//                c /= 10;
//            }
//            ret += '-';
//            reverse(ret.begin(), ret.end());
//        }
//        else {
//            while (c)
//            {
//                int t = c % 10;
//                ret += t + '0';
//                c /= 10;
//            }
//            reverse(ret.begin(), ret.end());
//        }
//        return ret;
//    }
//    int evalRPN(vector<string>& tokens) {
//        stack<string> num;
//        for (int i = 0; i < tokens.size(); i++)
//        {
//            if (tokens[i] == "+" || tokens[i] == "-"
//                || tokens[i] == "*" || tokens[i] == "/")
//            {
//                string str1 = num.top();
//                int a = 0;
//                num.pop();
//                a = StrToInt(str1);
//                //cout<<a<<endl;
//                string str2 = num.top();
//                int b = 0;
//                num.pop();
//                b = StrToInt(str2);
//                //cout<<b<<endl;
//                int c;
//                if (tokens[i] == "+")
//                {
//                    c = a + b;
//                    string tmp;
//                    tmp = IntToStr(c);
//                    num.push(tmp);
//                }
//                else if (tokens[i] == "-")
//                {
//                    c = b - a;
//                    string tmp;
//                    tmp = IntToStr(c);
//                    num.push(tmp);
//                }
//                else if (tokens[i] == "*")
//                {
//                    c = a * b;
//                    string tmp;
//                    tmp = IntToStr(c);
//                    num.push(tmp);
//                }
//                else {
//                    c = b / a;
//                    string tmp;
//                    tmp = IntToStr(c);
//                    num.push(tmp);
//                }
//            }
//            else
//            {
//                num.push(tokens[i]);
//            }
//        }
//        string s = num.top();
//        int a = StrToInt(s);
//        return a;
//    }
//};
//
//
//
//
//
////Day41
////棋子翻转
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         *
//         * @param A int整型vector<vector<>>
//         * @param f int整型vector<vector<>>
//         * @return int整型vector<vector<>>
//         */
//    void reverse_A(vector<vector<int> >& A, int i, int j)
//    {
//        if (i - 1 >= 0)
//        {
//            if (A[i - 1][j] == 0)
//                A[i - 1][j] = 1;
//            else
//                A[i - 1][j] = 0;
//        }
//        if (j - 1 >= 0)
//        {
//            if (A[i][j - 1] == 0)
//                A[i][j - 1] = 1;
//            else
//                A[i][j - 1] = 0;
//        }
//        if (j + 1 < A[i].size())
//        {
//            if (A[i][j + 1] == 0)
//                A[i][j + 1] = 1;
//            else
//                A[i][j + 1] = 0;
//        }
//        if (i + 1 < A.size())
//        {
//            if (A[i + 1][j] == 0)
//                A[i + 1][j] = 1;
//            else
//                A[i + 1][j] = 0;
//        }
//    }
//    vector<vector<int> > flipChess(vector<vector<int> >& A, vector<vector<int> >& f) {
//        // write code here
//        for (int k = 0; k < f.size(); k++)
//        {
//            int x = f[k][0], y = f[k][1];
//            for (int i = 0; i < A.size(); i++)
//            {
//                for (int j = 0; j < A[i].size(); j++)
//                {
//                    if (i == x - 1 && j == y - 1)
//                    {
//                        reverse_A(A, i, j);
//                    }
//                }
//            }
//        }
//        return A;
//    }
//};
//
//
////宵暗的妖怪
//#include <iostream>
//#include <vector>
//using namespace std;
//
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    int max = 0;
//    int time;
//    if (n % 2 == 1)
//        time = n / 2 + 1;
//    else
//        time = n / 2;
//    int i = 1;
//    for (int i = 1; i <= time; i++)
//    {
//        int sum = 0;
//        for (int j = i; j < v.size() - 1; j += 3)
//        {
//            sum += v[j];
//        }
//        if (sum > max)
//            max = sum;
//    }
//    cout << max;
//}
//// 64 位输出请用 printf("%lld")
//
//
////过桥
//#include <iostream>
//#include <vector>
//using namespace std;
//
//void Sum(vector<int> v, int& time, int n)
//{
//    if (n <= 0)
//        return;
//    int dp = 1;
//    for (int i = n - 1; i >= 0; i--)
//    {
//        if (v[i] >= dp)
//        {
//            time++;
//            Sum(v, time, i);
//        }
//        dp++;
//    }
//}
//int main() {
//    int n;
//    cin >> n;
//    vector<int> v;
//    v.resize(n);
//    for (int i = 0; i < n; i++)
//    {
//        cin >> v[i];
//    }
//    for (int i = 0; i < n; i++)
//    {
//        if (v[i] > 0)
//            break;
//        if (i == n - 1)
//        {
//            cout << -1;
//            return 0;
//        }
//    }
//    vector<int> di;
//    di.resize(n, 0);
//    int time = 0;
//    Sum(v, time, n - 1);
//    cout << time;
//}
//// 64 位输出请用 printf("%lld")
//
//
//
//
//
////Day47
////矩阵转置
//#include <iostream>
//using namespace std;
//
//int main() {
//    int a, b;
//    cin >> a >> b;
//    int arr[a][b];
//    for (int i = 0; i < a; i++)
//    {
//        for (int j = 0; j < b; j++)
//            cin >> arr[i][j];
//    }
//    for (int j = 0; j < b; j++)
//    {
//        for (int i = 0; i < a; i++)
//        {
//            cout << arr[i][j] << ' ';
//        }
//        cout << endl;
//    }
//}
//// 64 位输出请用 printf("%lld")
//
////4个选项
//
////接雨水
//#include <algorithm>
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * max water
//         * @param arr int整型vector the array
//         * @return long长整型
//         */
//    long long maxWater(vector<int>& arr) {
//        // write code here
//        vector<int> a, b, c;
//        a.resize(arr.size());
//        b.resize(arr.size());
//        c.resize(arr.size());
//        //vector<int>::iterator it=arr.begin();
//        int max_l = arr[0];
//        for (int i = 0; i < arr.size(); i++)
//        {
//            if (max_l < arr[i])
//            {
//                max_l = arr[i];
//            }
//            a[i] = max_l;
//        }
//        int max_r = arr[arr.size() - 1];
//        for (int i = arr.size() - 1; i >= 0; i--)
//        {
//            if (max_r < arr[i])
//            {
//                max_r = arr[i];
//            }
//            b[i] = max_r;
//        }
//        for (int i = 0; i < arr.size(); i++)
//        {
//            int min = std::min(a[i], b[i]);
//            c[i] = min;
//        }
//        int ret = 0;
//        for (int i = 0; i < arr.size(); i++)
//        {
//            ret += c[i] - arr[i];
//        }
//        return ret;
//    }
//};
//
//
//
//
//
//
////Day48
////疯狂的自我检索者
//#include <iostream>
//using namespace std;
//
//int main() {
//    int n, m;
//    cin >> n >> m;
//    int arr[n - m];
//
//    for (int i = 0; i < n - m; i++)
//        cin >> arr[i];
//    double sum = 0;
//    double min = 0, max = 0;
//    if (n == m)
//    {
//        min = 1; max = 5;
//    }
//    else {
//        for (int i = 0; i < n - m; i++)
//            sum += arr[i];
//        min = (sum + 1.0 * (m)) / n;
//        max = (sum + 5.0 * (m)) / n;
//    }
//    printf("%.5lf %.5lf", min, max);
//}
//// 64 位输出请用 printf("%lld")
//
//
////栈和排序
//#include <stack>
//class Solution {
//public:
//        /**
//         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//         *
//         * 栈排序
//         * @param a int整型vector 描述入栈顺序
//         * @return int整型vector
//         */
//    int find_max(vector<int>& a, int n)
//    {
//        int max = a[n];
//        for (int i = n; i < a.size(); i++)
//        {
//            if (a[i] > max)
//                max = a[i];
//        }
//        return max;
//    }
//    vector<int> solve(vector<int>& a) {
//        // write code here
//        int max = find_max(a, 0);
//        vector<int> st;
//        vector<int> ret;
//        int i = 0;
//        while (i < a.size())
//        {
//            int tmp = a[i];
//            if (tmp != max)
//            {
//                st.push_back(tmp);
//            }
//            else {
//                ret.push_back(tmp);
//                if (i < a.size() - 1)
//                    max = find_max(a, i + 1);
//            }
//            i++;
//        }
//        for (int j = st.size() - 1; j >= 0; j--)
//        {
//            ret.push_back(st[j]);
//        }
//        // while(st.empty())
//        // {
//        //     int t=st.top();
//        //     ret.push_back(t);
//        //     st.pop();
//        // }
//        return ret;
//    }
//};
//
//
////Z字变换
//class Solution {
//public:
//    string convert(string s, int numRows) {
//        if (numRows == 1)
//            return s;
//        else if (s.size() < numRows)
//            return s;
//        else
//        {
//            int c = (numRows - 1) * 2;
//            string ret;
//            for (int i = 0; i < numRows; i++)
//            {
//                if (i == 0 || i == numRows - 1)
//                {
//                    for (int j = i; j < s.size(); j += c)
//                    {
//                        ret.push_back(s[j]);
//                    }
//                }
//                else
//                {
//                    int c1 = c - 2 * i;
//                    int c2 = c - 2 * (numRows - 1 - i);
//                    int j = i;
//                    ret.push_back(s[j]);
//                    while (j < s.size())
//                    {
//                        j += c1;
//                        if (j < s.size())
//                            ret.push_back(s[j]);
//                        else
//                            break;
//                        j += c2;
//                        if (j < s.size())
//                            ret.push_back(s[j]);
//                        else
//                            break;
//
//                    }
//                }
//            }
//            return ret;
//        }
//    }
//};
//
//
//
////二叉树的最大深度
//class Solution {
//public:
//    int maxDepth(TreeNode* root) {
//        if (root == NULL)
//            return 0;
//        int left = maxDepth(root->left);
//        int right = maxDepth(root->right);
//        int max = left > right ? left : right;
//        return max + 1;
//    }
//};
//
//
////判断树是否相同
//class Solution {
//public:
//    bool isSameTree(TreeNode* p, TreeNode* q) {
//        if (p == NULL && q == NULL)
//            return true;
//        else if ((p == NULL && q != NULL) || (p != NULL && q == NULL))
//            return false;
//        if (p->val != q->val)
//            return false;
//        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
//    }
//};
//
//
//
////动态规划
////解码方法
//class Solution {
//public:
//    int numDecodings(string s) {
//        vector<int> v;
//        v.resize(s.size());
//        if (s.size() == 1)
//        {
//            if ('1' <= s[0] && s[0] <= '9')
//                v[0] = 1;
//            else
//                v[0] = 0;
//            return v[0];
//        }
//        else if (s.size() == 2)
//        {
//            if ('1' <= s[0] && s[0] <= '9')
//                v[0] = 1;
//            else
//                v[0] = 0;
//            if (('1' <= s[1] && s[1] <= '9' && v[0] == 1) && ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26))
//                v[1] = 2;
//            else if (('1' <= s[1] && s[1] <= '9' && v[0] == 1) || ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26))
//                v[1] = 1;
//            else
//                v[1] = 0;
//            return v[1];
//        }
//        else
//        {
//            if ('1' <= s[0] && s[0] <= '9')
//                v[0] = 1;
//            else
//                v[0] = 0;
//            if (('1' <= s[1] && s[1] <= '9' && v[0] == 1) && ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26))
//                v[1] = 2;
//            else if (('1' <= s[1] && s[1] <= '9' && v[0] == 1) || ((s[0] - '0') * 10 + (s[1] - '0') >= 10 && (s[0] - '0') * 10 + (s[1] - '0') <= 26))
//                v[1] = 1;
//            else
//                v[1] = 0;
//            for (int i = 2; i < s.size(); i++)
//            {
//                int tmp1 = 0;
//                int tmp2 = 0;
//                if ('1' <= s[i] && s[i] <= '9')
//                    tmp1 = v[i - 1];
//                if ((s[i - 1] - '0') * 10 + (s[i] - '0') >= 10 && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26)
//                    tmp2 = v[i - 2];
//                v[i] = tmp1 + tmp2;
//            }
//            return v[v.size() - 1];
//        }
//
//    }
//};
//
//
////不同路径
//class Solution {
//public:
//    int uniquePaths(int m, int n) {
//        vector<vector<int>> dp;
//        dp.resize(m);
//        for (int i = 0; i < m; i++)
//        {
//            dp[i].resize(n);
//        }
//        for (int i = 0; i < m; i++)
//        {
//            dp[i][0] = 1;
//        }
//        for (int i = 0; i < n; i++)
//        {
//            dp[0][i] = 1;
//        }
//        for (int i = 1; i < m; i++)
//        {
//            for (int j = 1; j < n; j++)
//            {
//                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
//            }
//        }
//        return dp[m - 1][n - 1];
//    }
//};
//
//
////不同路径2
//class Solution {
//public:
//    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
//        vector<vector<int>> dp = obstacleGrid;
//        int r = dp.size(), c = dp[0].size();
//        if (obstacleGrid[r - 1][c - 1] == 1 || obstacleGrid[0][0] == 1)
//            return 0;
//        for (int i = 0; i < r; i++)
//        {
//            int flag = 0;
//            for (int j = 0; j < c; j++)
//            {
//                if (obstacleGrid[i][j] == 1)
//                    flag++;
//            }
//            if (flag == c)
//                return 0;
//        }
//        for (int i = 0; i < c; i++)
//        {
//            int flag = 0;
//            for (int j = 0; j < r; j++)
//            {
//                if (obstacleGrid[j][i] == 1)
//                    flag++;
//            }
//            if (flag == r)
//                return 0;
//        }
//        for (int i = 0; i < r; i++)
//        {
//            for (int j = 0; j < c; j++)
//            {
//                if (dp[i][j] == 1)
//                    dp[i][j] = -1;
//            }
//        }
//
//        for (int i = 0; i < r; i++)
//        {
//            if (dp[i][0] != -1)
//            {
//                dp[i][0] = 1;
//            }
//        }
//        for (int i = 0; i < c; i++)
//        {
//            if (dp[0][i] != -1)
//            {
//                dp[0][i] = 1;
//            }
//        }
//        for (int i = 1; i < r; i++)
//        {
//            for (int j = 1; j < c; j++)
//            {
//                if (dp[i][j] != -1)
//                {
//                    if (dp[i - 1][j] != -1)
//                        dp[i][j] += dp[i - 1][j];
//                    if (dp[i][j - 1] != -1)
//                        dp[i][j] += dp[i][j - 1];
//                }
//            }
//        }
//        return dp[r - 1][c - 1];
//    }
//};
//
//
//
////翻转链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    void push_front(ListNode*& head, int v)
//    {
//        ListNode* tmp = new(ListNode);
//        tmp->val = v;
//        tmp->next = head;
//        head = tmp;
//    }
//
//    ListNode* reverseList(ListNode* head) {
//        if (head == NULL)
//            return NULL;
//        ListNode* newhead = new ListNode;
//        newhead->val = head->val;
//        newhead->next = NULL;
//        head = head->next;
//        while (head != NULL)
//        {
//            push_front(newhead, head->val);
//            head = head->next;
//        }
//        return newhead;
//    }
//};
//
//
////平衡二叉树
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    int deep(TreeNode* root)
//    {
//        if (root == NULL)
//            return 0;
//        int l = 1 + deep(root->left);
//        int r = 1 + deep(root->right);
//        return max(l, r);
//    }
//    bool isBalanced(TreeNode* root) {
//        if (root == NULL)
//            return true;
//        int L = deep(root->left);
//        int R = deep(root->right);
//        if (abs(R - L) > 1)
//            return false;
//        return isBalanced(root->left) && isBalanced(root->right);
//    }
//};
//
//
////最长回文子串
//class Solution {
//public:
//    bool Ishui(string s, int x, int y)
//    {
//        while (x < y)
//        {
//            if (s[x] == s[y])
//            {
//                x++; y--;
//            }
//            else
//                return false;
//        }
//        return true;
//    }
//    string longestPalindrome(string s) {
//        int max = 0, max_i = 0, max_j = 0;
//        for (int i = 0; i < s.size(); i++)
//        {
//            int j = s.size() - 1;
//            while (j > i)
//            {
//                if (s[j] == s[i])
//                {
//                    if (Ishui(s, i, j) && max < j - i)
//                    {
//                        max = j - i;
//                        max_i = i;
//                        max_j = j;
//                    }
//                }
//                j--;
//            }
//        }
//        string ret;
//        for (int i = max_i; i <= max_j; i++)
//        {
//            ret += s[i];
//        }
//        return ret;
//    }
//};
//
//
////有效括号
//class Solution {
//public:
//    bool isValid(string s) {
//        stack<char> sc;
//        for (int i = 0; i < s.size(); i++)
//        {
//            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
//            {
//                sc.push(s[i]);
//            }
//            else
//            {
//                if (!sc.empty())
//                {
//                    if (s[i] == ')' && sc.top() == '(')
//                        sc.pop();
//                    else if (s[i] == ']' && sc.top() == '[')
//                        sc.pop();
//                    else if (s[i] == '}' && sc.top() == '{')
//                        sc.pop();
//                    else
//                        return false;
//                }
//                else
//                    return false;
//            }
//        }
//        if (sc.empty())
//            return true;
//        else
//            return false;
//    }
//};
//
//
////用队列实现栈
//class MyStack {
//public:
//    MyStack() {}
//
//    void push(int x) {
//        if (q1.empty() && q2.empty())
//            q1.push(x);
//        else if (!q1.empty())
//            q1.push(x);
//        else
//            q2.push(x);
//    }
//
//    int pop() {
//        int ret;
//        if (!q1.empty())
//        {
//            while (q1.size() > 1)
//            {
//                q2.push(q1.front());
//                q1.pop();
//            }
//            ret = q1.front();
//            q1.pop();
//        }
//        else
//        {
//            while (q2.size() > 1)
//            {
//                q1.push(q2.front());
//                q2.pop();
//            }
//            ret = q2.front();
//            q2.pop();
//        }
//        return ret;
//    }
//
//    int top() {
//        int ret;
//        if (!q1.empty())
//        {
//            while (q1.size() > 1)
//            {
//                q2.push(q1.front());
//                q1.pop();
//            }
//            ret = q1.front();
//            q2.push(q1.front());
//            q1.pop();
//        }
//        else
//        {
//            while (q2.size() > 1)
//            {
//                q1.push(q2.front());
//                q2.pop();
//            }
//            ret = q2.front();
//            q1.push(q2.front());
//            q2.pop();
//        }
//        return ret;
//    }
//
//    bool empty() {
//        return q1.empty() && q2.empty();
//    }
//    queue<int> q1;
//    queue<int> q2;
//};
//
///**
// * Your MyStack object will be instantiated and called as such:
// * MyStack* obj = new MyStack();
// * obj->push(x);
// * int param_2 = obj->pop();
// * int param_3 = obj->top();
// * bool param_4 = obj->empty();
// */
//
//
//
////用栈实现队列
//class MyQueue {
//public:
//    MyQueue() {}
//
//    void push(int x) {
//        in.push(x);
//    }
//
//    int pop() {
//        int tmp;
//        if (!out.empty())
//        {
//            tmp = out.top();
//            out.pop();
//            return tmp;
//        }
//        else
//        {
//            while (!in.empty())
//            {
//                out.push(in.top());
//                in.pop();
//            }
//            tmp = out.top();
//            out.pop();
//            return tmp;
//        }
//    }
//
//    int peek() {
//        int tmp;
//        if (!out.empty())
//        {
//            tmp = out.top();
//            return tmp;
//        }
//        else
//        {
//            while (!in.empty())
//            {
//                out.push(in.top());
//                in.pop();
//            }
//            tmp = out.top();
//            return tmp;
//        }
//    }
//
//    bool empty() {
//        return in.empty() && out.empty();
//    }
//    stack<int> in;
//    stack<int> out;
//};
//
///**
// * Your MyQueue object will be instantiated and called as such:
// * MyQueue* obj = new MyQueue();
// * obj->push(x);
// * int param_2 = obj->pop();
// * int param_3 = obj->peek();
// * bool param_4 = obj->empty();
// */
//
//
//
//
////692. 前K个高频单词
//class Solution {
//public:
//    struct Wordcmp
//    {
//        bool operator()(const pair<string, int>& m1, const pair<string, int>& m2)
//        {
//
//            return m1.second > m2.second || (m1.second == m2.second && m1.first < m2.first);
//            //return m1.second>m2.second;
//        }
//    };
//    vector<string> topKFrequent(vector<string>& words, int k) {
//        map<string, int> si;
//        for (int i = 0; i < words.size(); i++)
//        {
//            si[words[i]]++;
//        }
//
//        //map里的每个节点都是pair<string,int>类型
//        vector<pair<string, int>> vp(si.begin(), si.end());
//        //sort  不能对map类型排序，所以要先把map转为vector
//        //sort快排会改变同样大小的数据的相对位置，稳定排序（归并）不会
//        //stable_sort(vp.begin(),vp.end(),Wordcmp());
//
//        sort(vp.begin(), vp.end(), Wordcmp());
//        vector<string> ret;
//
//        for (int i = 0; i < k; i++)
//        {
//            ret.push_back(vp[i].first);
//        }
//        return ret;
//    }
//};
//
//
//
////349. 两个数组的交集
////用set实现
//class Solution {
//public:
//    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
//        //for(auto e:nums1)
//        set<int> s1(nums1.begin(), nums1.end());
//        set<int> s2(nums2.begin(), nums2.end());
//        vector<int> ret;
//        set<int> tmp;
//        for (auto e : s2)
//        {
//            if ((s1.insert(e).second == false))
//            {
//                tmp.insert(e);
//            }
//        }
//        for (auto e : tmp)
//            ret.push_back(e);
//        return ret;
//    }
//};
//
//
//
////移除元素
//class Solution {
//public:
//    int removeElement(vector<int>& nums, int val) {
//        int l = 0;
//        for (int r = 0; r < nums.size(); r++)
//        {
//            if (nums[r] != val)
//            {
//                nums[l] = nums[r];
//                l++;
//            }
//        }
//        return l;
//    }
//};
//
//
////删除有序数组中的重复项
////解法一
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int i = 0, j = 1;
//        while (j < nums.size())
//        {
//            if (nums[i] == nums[j])
//            {
//                while (j < nums.size() && nums[i] == nums[j])
//                    j++;
//                if (j < nums.size())
//                {
//                    i++;
//                    nums[i] = nums[j];
//                }
//            }
//            else
//            {
//                i++; j++;
//            }
//        }
//        return i + 1;
//    }
//};
////优化上述双指针后，代码如下
//class Solution {
//public:
//    int removeDuplicates(vector<int>& nums) {
//        int i = 0, j = 1;
//        for (j; j < nums.size(); j++)
//        {
//            if (nums[i] != nums[j])
//            {
//                i++;
//                nums[i] = nums[j];
//            }
//        }
//        return i + 1;
//    }
//};
//
//
////合并两个有序数组
//class Solution {
//public:
//    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
//        int i = 0, j = 0;
//        vector<int> ret;
//        while (i < m && j < n)
//        {
//            if (nums1[i] < nums2[j]) {
//                ret.push_back(nums1[i]);
//                i++;
//            }
//            else {
//                ret.push_back(nums2[j]);
//                j++;
//            }
//        }
//        while (i < m)
//        {
//            ret.push_back(nums1[i]);
//            i++;
//        }
//        while (j < n)
//        {
//            ret.push_back(nums2[j]);
//            j++;
//        }
//        for (int x = 0; x < n + m; x++)
//        {
//            nums1[x] = ret[x];
//        }
//    }
//};
//
//
////203. 移除链表元素
////解法1
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//    void PushBack(ListNode*& head, int val)
//    {
//        ListNode* newnode = new ListNode;
//        newnode->val = val;
//        newnode->next = nullptr;
//        if (head == nullptr)
//        {
//            head = newnode;
//            return;
//        }
//        ListNode* cur = head;
//        while (cur->next != nullptr)
//        {
//            cur = cur->next;
//        }
//        cur->next = newnode;
//    }
//
//public:
//    ListNode* removeElements(ListNode* head, int val) {
//        ListNode* ret = nullptr;
//        ListNode* cur = head;
//        while (cur != nullptr)
//        {
//            if (cur->val != val)
//                PushBack(ret, cur->val);
//            cur = cur->next;
//        }
//        return ret;
//    }
//};
////解法二
//class Solution {
//public:
//    ListNode* removeElements(ListNode* head, int val) {
//        while (head != nullptr && head->val == val)
//        {
//            head = head->next;
//        }
//        ListNode* newhead = head;
//        ListNode* cur = newhead;
//        while (cur != nullptr && cur->next != nullptr)
//        {
//            if (cur->next->val == val)
//            {
//                cur->next = cur->next->next;
//                continue;   //删除了一个节点后要重新上去判断后补上的节点是不是要删除的
//            }
//            cur = cur->next;
//        }
//        return newhead;
//    }
//};
//
//
//
//
////反转链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//    void PushFont(ListNode*& ret, ListNode* cur)
//    {
//        if (ret == nullptr)
//        {
//            ret = new ListNode(cur->val, nullptr);
//            return;
//        }
//        ListNode* tmp = new ListNode(cur->val, ret);
//        ret = tmp;
//    }
//public:
//    ListNode* reverseList(ListNode* head) {
//        ListNode* cur = head;
//        ListNode* ret = nullptr;
//        while (cur)
//        {
//            PushFont(ret, cur);
//            cur = cur->next;
//        }
//        return ret;
//    }
//};
////迭代写法（优化后）
//class Solution {
//public:
//    ListNode* reverseList(ListNode* head) {
//        ListNode* prev = nullptr;
//        ListNode* cur = head;
//        //cur负责遍历head链表
//        //prev时刻表示头节点
//        while (cur)
//        {
//            //tmp临时存储cur，用于头插
//            ListNode* tmp = cur;
//            cur = cur->next;  //先将cur往后遍历
//            //再实现头插
//            tmp->next = prev;
//            prev = tmp;
//        }
//        return prev;
//    }
//};
//
//
////876. 链表的中间结点
//class Solution {
//public:
//    ListNode* middleNode(ListNode* head) {
//        int len = 0;
//        ListNode* cur = head;
//        while (cur)
//        {
//            cur = cur->next;
//            len++;
//        }
//        len = len / 2;
//        ListNode* ret = head;
//        while (len)
//        {
//            ret = ret->next;
//            len--;
//        }
//        return ret;
//    }
//};
//
//
//
////合并两个有序链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
//        ListNode* ret = nullptr;
//        if (list1 == nullptr)
//            return list2;
//        if (list2 == nullptr)
//            return list1;
//        if (list1->val > list2->val)
//        {
//            ret = list2;
//            list2 = list2->next;
//        }
//        else
//        {
//            ret = list1;
//            list1 = list1->next;
//        }
//        ListNode* tmp = ret;
//        while (list1 && list2)
//        {
//            if (list1->val > list2->val)
//            {
//                tmp->next = list2;
//                list2 = list2->next;
//            }
//            else
//            {
//                tmp->next = list1;
//                list1 = list1->next;
//            }
//            tmp = tmp->next;
//        }
//        if (list1 != nullptr)
//            tmp->next = list1;
//        if (list2 != nullptr)
//            tmp->next = list2;
//        return ret;
//    }
//};
//
//
////链表分割
///*
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};*/
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        if (pHead == nullptr)
//            return pHead;
//        ListNode* small = new ListNode(0);
//        ListNode* big = new ListNode(0);
//        ListNode* tmp1 = small;
//        ListNode* tmp2 = big;
//        ListNode* cur = pHead;
//        while (cur != nullptr)
//        {
//            if (cur->val < x)
//            {
//                tmp1->next = cur;
//                tmp1 = tmp1->next;
//            }
//            else
//            {
//                tmp2->next = cur;
//                tmp2 = tmp2->next;
//            }
//            cur = cur->next;
//        }
//        tmp2->next = nullptr;
//        tmp1->next = big->next;
//        return small->next;
//    }
//};
//
//
//
////判断链表是否回文
///*
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};*/
//class PalindromeList {
//    ListNode* Reverse(ListNode* head)
//    {
//        ListNode* cur = head;
//        ListNode* prev = nullptr;
//        ListNode* tmp;
//        while (cur)
//        {
//            tmp = cur;
//            cur = cur->next;
//            tmp->next = prev;
//            prev = tmp;
//        }
//        return prev;
//    }
//public:
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        int len = 0;
//        ListNode* cur1 = A;
//        while (cur1)
//        {
//            len += 1;
//            cur1 = cur1->next;
//        }
//        len /= 2;
//        ListNode* rev = A;
//        while (len)
//        {
//            rev = rev->next;
//            len--;
//        }
//        ListNode* ret = Reverse(rev);
//        ListNode* cur2 = A;
//        while (ret)
//        {
//            //printf("%d ",ret->val);
//            if (cur2->val != ret->val)
//                return false;
//            ret = ret->next;
//            cur2 = cur2->next;
//        }
//        return true;
//    }
//};
//
//
////160. 相交链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode(int x) : val(x), next(NULL) {}
// * };
// */
//class Solution {
//public:
//    ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
//        if (headA == nullptr || headB == nullptr)
//            return nullptr;
//        ListNode* cur1 = headA;
//        ListNode* cur2 = headB;
//        int len1 = 0, len2 = 0;
//        while (cur1)
//        {
//            len1++;
//            cur1 = cur1->next;
//        }
//        while (cur2)
//        {
//            len2++;
//            cur2 = cur2->next;
//        }
//        if (len1 > len2)
//        {
//            int cha = len1 - len2;
//            while (cha)
//            {
//                headA = headA->next;
//                cha--;
//            }
//        }
//        else {
//            int cha = len2 - len1;
//            while (cha)
//            {
//                headB = headB->next;
//                cha--;
//            }
//        }
//        while (headA)
//        {
//            if (headA == headB)
//                return headA;
//            headA = headA->next;
//            headB = headB->next;
//        }
//        return nullptr;
//    }
//};
//
//
////141. 环形链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode(int x) : val(x), next(NULL) {}
// * };
// */
//class Solution {
//public:
//    bool hasCycle(ListNode* head) {
//        ListNode* fast = head;
//        ListNode* slow = head;
//        //快慢指针
//        while (slow && fast && fast->next)
//        {
//            slow = slow->next;
//            fast = fast->next->next;
//            if (slow == fast)
//                return true;
//        }
//        return false;
//    }
//};
//
//
//
//
////142. 环形链表 II
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode(int x) : val(x), next(NULL) {}
// * };
// */
//class Solution {
//public:
//    ListNode* detectCycle(ListNode* head) {
//        //快慢指针找相遇点
//        ListNode* fast = head;
//        ListNode* slow = head;
//        while (slow && fast && fast->next)
//        {
//            slow = slow->next;
//            fast = fast->next->next;
//            if (slow == fast)
//                break;
//        }
//        if (slow == nullptr || fast == nullptr || fast->next == nullptr)
//        {
//            return nullptr;
//        }
//        //特殊情况，环在头节点
//        if (head == slow)
//            return head;
//        //计算从起点到相遇点的距离和绕环的距离
//        //二者相减则是（起点距离到环起点的长度）-（相遇点到环起点的长度）
//        //二者的更长的部分减去长的部分，从相同距离出发，相遇时即为环起点
//        int len1 = 0, len2 = 1;
//        ListNode* cur1 = head;
//        ListNode* cur2 = slow->next;
//        while (cur1 != slow)
//        {
//            len1++;
//            cur1 = cur1->next;
//        }
//        while (cur2 != slow)
//        {
//            len2++;
//            cur2 = cur2->next;
//        }
//        ListNode* ret1 = head;
//        ListNode* ret2 = slow;
//        if (len1 > len2)
//        {
//            int c = len1 - len2;
//            while (c)
//            {
//                ret1 = ret1->next;
//                c--;
//            }
//        }
//        else
//        {
//            int c = len2 - len1;
//            while (c)
//            {
//                ret2 = ret2->next;
//                c--;
//            }
//        }
//        while (ret1 && ret2)
//        {
//            ret1 = ret1->next;
//            ret2 = ret2->next;
//            if (ret1 == ret2)
//                break;
//        }
//        return ret1;
//    }
//};
//
//
//
////138. 随机链表的复制
///*
//// Definition for a Node.
//class Node {
//public:
//    int val;
//    Node* next;
//    Node* random;
//
//    Node(int _val) {
//        val = _val;
//        next = NULL;
//        random = NULL;
//    }
//};
//*/
//
//class Solution {
//public:
//    Node* copyRandomList(Node* head) {
//        //复制原链表的val和next
//        if (head == NULL)
//            return NULL;
//        Node* ret = new Node(head->val);
//        Node* cur1 = head->next;
//        Node* cur2 = ret;
//        while (cur1)
//        {
//            Node* tmp = new Node(cur1->val);
//            cur2->next = tmp;
//            cur1 = cur1->next;
//            cur2 = cur2->next;
//        }
//        //添加random内容
//        cur1 = head;
//        cur2 = ret;
//        while (cur1)
//        {
//            if (cur1->random == NULL)
//                cur2->random = NULL;
//            else {
//                int len = 0;
//                Node* tmp1 = head;
//                Node* tmp2 = cur1->random;
//                while (tmp1 != tmp2)
//                {
//                    len++;
//                    tmp1 = tmp1->next;
//                }
//                Node* tmp3 = ret;
//                while (len)
//                {
//                    tmp3 = tmp3->next;
//                    len--;
//                }
//                cur2->random = tmp3;
//            }
//            cur2 = cur2->next;
//            cur1 = cur1->next;
//        }
//        return ret;
//    }
//};
//
//
//
//
////验证回文串
////新建一个字符串
//class Solution {
//public:
//    bool isPalindrome(string s) {
//        string ret;
//        string::iterator si = s.begin();
//        for (auto e : s)
//        {
//            if (e >= 'A' && e <= 'Z')
//            {
//                e += 32;
//                ret += e;
//            }
//            else if (e >= 'a' && e <= 'z')
//                ret += e;
//            else if (e >= '0' && e <= '9')
//                ret += e;
//        }
//        string::iterator si1 = ret.begin();
//        string::iterator si2 = ret.end() - 1;
//
//        while (si1 < si2)
//        {
//            if (*si1 != *si2)
//                return false;
//            si1++;
//            si2--;
//        }
//        return true;
//    }
//};
////优化后
//class Solution {
//public:
//    bool isPalindrome(string s) {
//        string ret;
//        string::iterator si = s.begin();
//        for (auto e : s)
//        {
//            if (e >= 'A' && e <= 'Z')
//            {
//                e += 32;
//                ret += e;
//            }
//            else if (e >= 'a' && e <= 'z')
//                ret += e;
//            else if (e >= '0' && e <= '9')
//                ret += e;
//        }
//        string::iterator si1 = ret.begin();
//        string::iterator si2 = ret.end() - 1;
//        while (si1 < si2)
//        {
//            while ((*si1 < 'a' && *si1>'z') || (*si1 < '0' && *si1>'9'))
//            {
//                if (*si1 >= 'A' && *si1 <= 'Z')
//                {
//                    *si1 += 32;
//                }
//                else if (*si1 >= 'a' && *si1 <= 'z');
//                else if (*si1 >= '0' && *si1 <= '9');
//                else {
//                    si1++;
//                }
//            }
//            while ((*si2 < 'a' && *si2>'z') || (*si2 < '0' && *si2>'9'))
//            {
//                if (*si2 >= 'A' && *si2 <= 'Z')
//                {
//                    *si2 += 32;
//                }
//                else if (*si2 >= 'a' && *si2 <= 'z');
//                else if (*si2 >= '0' && *si2 <= '9');
//                else {
//                    si2--;
//                }
//            }
//            if (*si1 != *si2)
//                return false;
//            si1++; si2--;
//        }
//        return true;
//    }
//};
////回文链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    ListNode* Reverse(ListNode* head)
//    {
//        ListNode* cur = head;
//        ListNode* prev = nullptr;
//        ListNode* tmp;
//        //头插
//        while (cur)
//        {
//            tmp = cur;
//            cur = cur->next;
//            tmp->next = prev;
//            prev = tmp;
//        }
//        return prev;
//    }
//    bool isPalindrome(ListNode* head) {
//        ListNode* cur = head;
//        int len = 0;
//        while (cur)
//        {
//            cur = cur->next;
//            len++;
//        }
//        len /= 2;
//        cur = head;
//        ListNode* cur2 = head;
//        while (len)
//        {
//            cur2 = cur2->next;
//            len--;
//        }
//        ListNode* ret = Reverse(cur2);
//        while (ret)
//        {
//            if (cur->val != ret->val)
//                return false;
//            cur = cur->next;
//            ret = ret->next;
//        }
//        return true;
//    }
//};
//
//
////验证回文串 II
//class Solution {
//public:
//    bool validPalindrome(string s) {
//        string::iterator si1 = s.begin();
//        string::iterator si2 = s.end() - 1;
//        while (si1 < si2)
//        {
//            if (*si1 != *si2)
//            {
//                bool ret = true;
//                string::iterator cur1 = si1 + 1;
//                string::iterator cur2 = si2;
//                while (cur1 < cur2)
//                {
//                    if (*cur1 != *cur2)
//                    {
//                        ret = false;
//                        break;
//                    }
//                    cur1++; cur2--;
//                }
//                if (ret == true)
//                    return true;
//                ret = true;
//                string::iterator cur3 = si1;
//                string::iterator cur4 = si2 - 1;
//                while (cur3 < cur4)
//                {
//                    if (*cur3 != *cur4)
//                    {
//                        ret = false;
//                        break;
//                    }
//                    cur3++; cur4--;
//                }
//                return ret;
//            }
//            else {
//                si1++; si2--;
//            }
//        }
//        return true;
//    }
//};
//
//
////回文链表
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//class Solution {
//public:
//    ListNode* Reverse(ListNode* head)
//    {
//        ListNode* cur = head;
//        ListNode* prev = nullptr;
//        while (cur)
//        {
//            ListNode* tmp = cur;
//            cur = cur->next;
//            tmp->next = prev;
//            prev = tmp;
//        }
//        return prev;
//    }
//    bool isPalindrome(ListNode* head) {
//        int len = 0;
//        ListNode* cur = head;
//        while (cur)
//        {
//            len++;
//            cur = cur->next;
//        }
//        len /= 2;
//        cur = head;
//        ListNode* cur2 = head;
//        while (len--)
//        {
//            cur2 = cur2->next;
//        }
//        ListNode* ret = Reverse(cur2);
//        while (ret)
//        {
//            if (ret->val != cur->val)
//                return false;
//            ret = ret->next;
//            cur = cur->next;
//        }
//        return true;
//    }
//};
//
//
//
//
//// 两数相加
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     ListNode *next;
// *     ListNode() : val(0), next(nullptr) {}
// *     ListNode(int x) : val(x), next(nullptr) {}
// *     ListNode(int x, ListNode *next) : val(x), next(next) {}
// * };
// */
//
//class Solution {
//public:
//    ListNode* Reverse(ListNode* head)
//    {
//        ListNode* cur = head;
//        ListNode* prev = nullptr;
//        while (cur)
//        {
//            ListNode* tmp = cur;
//            cur = cur->next;
//            tmp->next = prev;
//            prev = tmp;
//        }
//        return prev;
//    }
//    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//        ListNode* cur1 = l1;
//        ListNode* cur2 = l2;
//        ListNode* ret = nullptr;
//        int add = 0;
//        while (cur1 && cur2)
//        {
//            int num = cur1->val + cur2->val;
//            if (add > 0)
//            {
//                num++;
//                add = 0;
//            }
//            if (num >= 10)
//            {
//                num -= 10;
//                add += 1;
//            }
//            ListNode* tmp = new ListNode(num, ret);
//            ret = tmp;
//            cur1 = cur1->next;
//            cur2 = cur2->next;
//        }
//        while (cur1)
//        {
//            int num = cur1->val;
//            if (add > 0)
//            {
//                num++;
//                add = 0;
//            }
//            if (num >= 10)
//            {
//                num -= 10;
//                add += 1;
//            }
//            ListNode* tmp = new ListNode(num, ret);
//            tmp->next = ret;
//            ret = tmp;
//            cur1 = cur1->next;
//        }
//        while (cur2)
//        {
//            int num = cur2->val;
//            if (add > 0)
//            {
//                num++;
//                add = 0;
//            }
//            if (num >= 10)
//            {
//                num -= 10;
//                add += 1;
//            }
//            ListNode* tmp = new ListNode(num, ret);
//            tmp->next = ret;
//            ret = tmp;
//            cur2 = cur2->next;
//        }
//        if (add > 0)
//        {
//            ListNode* tmp = new ListNode(1, ret);
//            tmp->next = ret;
//            ret = tmp;
//        }
//        ListNode* Ret = Reverse(ret);
//        return Ret;	
//    }
//};

////测试隐式类型转换的常引用
//int main()
//{
//	double d = 1.5;
//	int& a = d;	
//
//	const int& b = d;
//
//	return 0;
//}
//
//
//
//
////965. 单值二叉树
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    bool isUnivalTree(TreeNode* root) {
//        if (root == nullptr)
//            return true;
//        if (root->left)
//            if (root->left->val != root->val)
//                return false;
//        if (root->right)
//            if (root->right->val != root->val)
//                return false;
//        return isUnivalTree(root->left) && isUnivalTree(root->right);
//    }
//};
//
//
//
////101. 对称二叉树
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    bool isSame(TreeNode* root1, TreeNode* root2)
//    {
//        if (root1 == root2 && root1 == nullptr)
//            return true;
//        if ((root1 == nullptr && root2 != nullptr) || (root1 != nullptr && root2 == nullptr))
//            return false;
//        if (root1->val != root2->val)
//            return false;
//        return isSame(root1->right, root2->left) && isSame(root1->left, root2->right);
//    }
//    bool isSymmetric(TreeNode* root) {
//        if (root == nullptr)
//            return true;
//        return isSame(root->right, root->left);
//    }
//};
//
//
//
////145. 二叉树的后序遍历
//class Solution {
//public:
//    void Postorder_Traversal(TreeNode* root, vector<int>& ret)
//    {
//        if (root == nullptr)
//            return;
//        Postorder_Traversal(root->left, ret);
//        Postorder_Traversal(root->right, ret);
//        ret.push_back(root->val);
//    }
//    vector<int> postorderTraversal(TreeNode* root) {
//        vector<int> ret;
//        Postorder_Traversal(root, ret);
//        return ret;
//    }
//};
//
//
//
////572. 另一棵树的子树
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    bool IsSame(TreeNode* root1, TreeNode* root2)
//    {
//        if (root1 == root2 && root1 == nullptr)
//        {
//            return true;
//        }
//        if ((root1 == nullptr && root2 != nullptr) || (root1 != nullptr && root2 == nullptr))
//        {
//            return false;
//        }
//        if (root1->val != root2->val)
//            return false;
//        return IsSame(root1->left, root2->left) && IsSame(root1->right, root2->right);
//    }
//    bool isSubtree(TreeNode* root, TreeNode* subRoot) {
//        if (root == nullptr)
//            return false;
//        if (root->val == subRoot->val)
//        {
//            bool ret = IsSame(root, subRoot);
//            if (ret == true)
//                return ret;
//        }
//        return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot);
//    }
//};
//
//
//
//
////层序遍历
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    vector<vector<int>> levelOrder(TreeNode* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr)
//            return ret;
//        ret.resize(1);
//        queue<TreeNode*> qt;
//        qt.push(root);
//        TreeNode* level = new TreeNode(INT_MAX);  //作为每行的分界符号
//        qt.push(level);
//        int i = 0;
//        while (!qt.empty())
//        {
//            TreeNode* tmp = qt.front();
//            qt.pop();
//            if (tmp == level) {
//                i++;
//                qt.push(level);
//                if (qt.front() == level)
//                    break;
//                ret.resize(i + 1);
//            }
//            else {
//                ret[i].push_back(tmp->val);
//                if (tmp->left != nullptr)
//                    qt.push(tmp->left);
//                if (tmp->right != nullptr)
//                    qt.push(tmp->right);
//            }
//        }
//        return ret;
//    }
//};
//
//
//
////107. 二叉树的层序遍历 II
///**
// * Definition for a binary tree node.
// * struct TreeNode {
// *     int val;
// *     TreeNode *left;
// *     TreeNode *right;
// *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
// *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
// *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// * };
// */
//class Solution {
//public:
//    vector<vector<int>> levelOrderBottom(TreeNode* root) {
//        vector<vector<int>> ret;
//        if (root == nullptr)
//            return ret;
//        ret.resize(1);
//        queue<TreeNode*> qt;
//        TreeNode* level = new TreeNode(INT_MAX);
//        qt.push(root);
//        qt.push(level);
//        int i = 0;
//        while (!qt.empty())
//        {
//            TreeNode* tmp = qt.front();
//            qt.pop();
//            if (tmp == level) {
//                i++;
//                ret.resize(i + 1);
//                qt.push(level);
//                if (qt.front() == level)
//                    break;
//            }
//            else {
//                ret[i].push_back(tmp->val);
//                if (tmp->left != nullptr)
//                    qt.push(tmp->left);
//                if (tmp->right != nullptr)
//                    qt.push(tmp->right);
//            }
//        }
//        ret.resize(i);
//        reverse(ret.begin(), ret.end());
//        return ret;
//    }
//};




//JZ64求1+2+3++n
//求1 + 2 +3+...+n，要求不能使用乘除法、位操作符、for、while、if、else
class A
{
public:
	A()
	{
		sum += c;
		c++;
	}
	//静态成员变量只能用静态成员函数访问到
	static int Getsum()
	{
		return sum;
	}
private:
	//声明两个静态成员，一个用于存总值，一个当做从1开始不断+1的变化值
	static int sum;
	static int c;
};
//定义静态成员变量
int A::sum = 0;
int A::c = 1;
//使用静态成员变量
class Solution {
public:
	int Sum_Solution(int n) {
		//n=10，正常情况下用变长数组来创建
		//A al[n];//变长数组
		//但当前版本不能使用变长数组，所以使用10来代替
		A a1[10];
		return A::Getsum();
	}
};
int main()
{
	Solution s;
	int ret=s.Sum_Solution(10);
	cout << ret << endl;
}